【完全背包】A005_LC_贴纸拼词（dp+状态压缩）

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们&＃xff0c;从而拼写出给定的目标字符串 target。

如果你愿意的话&＃xff0c;你可以不止一次地使用每一张贴纸&＃xff0c;而且每一张贴纸的数量都是无限的。

拼出目标 target 所需的最小贴纸数量是多少&＃xff1f;如果任务不可能&＃xff0c;则返回 -1。

示例 1&＃xff1a;
输入&＃xff1a;
["with", "example", "science"], "thehat"
输出&＃xff1a;
3解释&＃xff1a;
我们可以使用 2 个 "with" 贴纸&＃xff0c;和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后&＃xff0c;就可以形成目标 “thehat“ 了。
此外&＃xff0c;这是形成目标字符串所需的最小贴纸数量。示例 2&＃xff1a;
输入&＃xff1a;
["notice", "possible"], "basicbasic"
输出&＃xff1a;
-1解释&＃xff1a;
我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。


提示&＃xff1a;

stickers 长度范围是 [1, 50]。
stickers 由小写英文单词组成&＃xff08;不带撇号&＃xff09;。
target 的长度在 [1, 15] 范围内&＃xff0c;由小写字母组成。
在所有的测试案例中&＃xff0c;所有的单词都是从 1000 个最常见的美国英语单词中随机选取的&＃xff0c;目标是两个随机单词的串联。
时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

方法一&＃xff1a;背包 &＃43; 状压

第一眼锁定是背包&＃xff0c;比较南翔的是如果状态表示&＃xff0c;但观察到 target 的长度只有 15&＃xff0c;嗯&＃xff0c;嘻嘻&＃xff0c;状压安排了…

思路

假设 m &＃61; target.size()&＃xff0c;cap &＃61; 1<

• 定义状态&＃xff1a;
  • f[i] 表示匹配状态为 i 时的最少贴纸数
• 思考初始化&＃xff1a;
  • f[0] &＃61; 0&＃xff0c;f[1…cap] &＃61; -1
• 思考状态转移方程&＃xff1a;
  • f[j] &＃61; min(f[j], f[i] &＃43; 1)
    • j 时用拼接贴纸状态 i 的基础上再加入新贴纸 s 的贡献后的状态&＃xff1b;
    • k 是 target 的第 k 位字符&＃xff0c;
• 思考输出&＃xff1a;f[cap-1]

class Solution {
public:int minStickers(vector<string>& ss, string& tar) {int m&＃61;tar.size(), cap&＃61;1<<m, f[cap];memset(f, -1, sizeof f); f[0]&＃61;0;for (string& s : ss) for (int i&＃61;0; i<cap; i&＃43;&＃43;) if (f[i]!&＃61;-1) {int j&＃61;i;for (char c : s) //获取s的贡献for (int k&＃61;0; k<m; k&＃43;&＃43;) {if (c&＃61;&＃61;tar[k] && (j&(1<<k)) &＃61;&＃61; 0) {j |&＃61; 1<<k;break;}}if (f[j] &＃61;&＃61; -1) f[j]&＃61;f[i]&＃43;1;else f[j]&＃61;min(f[j], f[i]&＃43;1);}return f[cap-1];}
};


复杂度分析

• 时间复杂度&＃xff1a;O(2m×n×m)O(2^m × n × m)O(2m×n×m)&＃xff0c;
• 空间复杂度&＃xff1a;O(2m)O(2^m)O(2m)