题目

我们有 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 由小写英文单词组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/stickers-to-spell-word
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

刚看完题目没有头绪，看到评论里的「这个」思路，当时只看到了方法一的BFS+状压，觉得有些难懂，结果想着想着就觉得肯定可以不用BFS而是用DP解，大不了慢一点，于是就有了下面的代码，虽然也写了挺长时间。

然后发现这个评论里方法三就是DP哈哈，然后官解思路也是这样，不过是递归的形式。

代码

DP+状态压缩

  1. class Solution {
  2.     public int minStickers(String[] stickers, String target) {
  3.         int n = target.length();
  4.         // 拼n个字母，用n个二进制位表示每一个字母是否拼出
  5.         int k = 1 << n;
  6.         // dp[i]表示拼出了i对应的二进制排列所需的贴纸数，最后n位都需要是1，返回dp[k-1]
  7.         int[] dp = new int[k];
  8.         Arrays.fill(dp, n + 1);
  9.         // 拼出空串需要0个贴纸
  10.         dp[0] = 0;
  11.         for (int i = 1; i < k; i++) {
  12.             for (String stick : stickers) {
  13.                 int g = i;
  14.                 int[] cnt = new int[26];
  15.                 for (char c : stick.toCharArray()) {
  16.                     cnt[c - 'a']++;
  17.                 }
  18.                 for (int j = 0; j < n; j++) {
  19.                     char c = target.charAt(j);
  20.                     // (i >> j & 1) == 1表示需要拼出c字母
  21.                     // cnt[c - 'a'] > 0表示字母c在stick中存在
  22.                     if ((i >> j & 1) == 1 && cnt[c - 'a'] > 0) {
  23.                         cnt[c - 'a']--;
  24.                         // 将g的倒数第j位从1变为0
  25.                         g ^= 1 << j;
  26.                     }
  27.                 }
  28.                 // 使用了stick之后，需要拼出的从i变成了g
  29.                 dp[i] = Math.min(dp[i], dp[g] + 1);
  30.             }
  31.         }
  32.         return dp[k - 1] == n + 1 ? -1 : dp[k - 1];
  33.     }
  34. }