【LeetCode】 贴纸拼词（动态规划）

691. 贴纸拼词 - 力扣（LeetCode）

一、题目

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：
输入： stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2：
输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示：

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i] 和 target 由小写英文单词组成

二、代码

class Solution {
    public int minStickers(String[] stickers, String target) {
        // 统计贴纸的词频 scount[i]表示第i张贴纸上每个字母的词频数量。这个题目和字符的排列顺序没关系，只和字符数量有关系
        int[][] scount = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            char[] tchars = stickers[i].toCharArray();
            
            for (int j = 0; j < tchars.length; j++) {
                scount[i][tchars[j] - 'a']++;
            }
        }

        // 这里不能用目标字符串的词频统计来作为递归传参，因为dp是一个HashMap，它的key需要用一个对象唯一标识，只有字符串能做到这一点
        // int[] tcount = new int[26];
        // char[] targetChars = target.toCharArray();
        // for (int i = 0; i < targetChars.length; i++) {
        //     tcount[targetChars[i] - 'a']++;
        // }

        HashMap<String, Integer> dp = new HashMap<>();

        int min = process(scount, target, dp);

        // 如果返回的是系统最大值，表示无法组成目标字符串
        return min == Integer.MAX_VALUE ? -1 : process(scount, target, dp);
    }
    public int process(int[][] scount, String rest, HashMap<String, Integer> dp) {
        // 如果已经有计算出来的结果了，就直接拿出来用
        if (dp.containsKey(rest)) {
            return dp.get(rest);
        }

        // 如果剩余的目标字符已经空了，就不需要贴纸了，直接返回0张贴纸
        if (rest.length() == 0) {
            return 0;
        }

        // 统计目标字符串的词频
        int[] tcount = new int[26];
        char[] targetChars = rest.toCharArray();
        for (int i = 0; i < targetChars.length; i++) {
            tcount[targetChars[i] - 'a']++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < scount.length; i++) {
            // 只有存在当前目标字符串中第一个字符的贴纸才会进入到递归分支。这个操作是剪枝优化，减少不必要的重复递归分支。这个操作并不印象最终结果，但是能减少递归分支数，提高执行效率
            if (scount[i][targetChars[0] - 'a'] > 0) {
                
                // 用贴纸的字符对目标字符串的字符进行冲减，并且生成新的目标字符串
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    int num = tcount[j] - scount[i][j];
                    // 注意，tcount是栈中的数据，下一次循环还要用呢，不能在这里就对其进行修改
                    //tcount[j] -= scount[i][j];
                    for (int k = 0; k < num; k++) {
                        sb.append((char) (j + 'a'));
                    }
                }
                String nextRest = sb.toString();

                // 取最小值
                min = Math.min(min, process(scount, nextRest, dp));
            }
        }
        // 上面的循环中少算了每一个递归分支的第一个贴纸数，所以在这里要加1。如果min仍然为空，说明无法组合出目标字符串
        min += (min ==  Integer.MAX_VALUE ? 0 : 1);
        // 放入dp记录下来
        dp.put(rest, min);
        return min;
    }
}

三、解题思路 

注意这道题目的每张贴纸都是无穷多的，想用多少张就用多少张，只要是可以拼出最后的目标字符串。所以这道题和字符的排列顺序无关，只和字符数量有关。

利用记忆化搜索，将计算好的结果存入到dp中，比肩重复计算。这道题在递归过程中用到了剪枝的技巧，减少不必要的递归分支，提高执行效率。