上一篇文章中的两道较为简单的题目都是通过 暴力递归 逐步修改成为 动态规划 ，并使用了严格的 dp表依赖 ，相信小伙伴对此有了初步的认识。
本文我们来练习一道 LeetCode 中 Hard 级别，不使用严格的表依赖的题目。
力扣691. 贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的 数量是无限 的。
返回你需要拼出 target 的 最小贴纸数量 。如果任务不可能，则返回 -1 。
示例 1：
输入: stickers = [“with”,“example”,“science”], target = “thehat”
输出: 3
解释：
使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。
把贴纸上的字母剪下来并重新排列后，形成目标 “thehat“ 了。
这是所需的最小贴纸数量。
示例 2:
输入: stickers = [“notice”,“possible”], target = “basicbasic”
输出： -1
解释： 我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。
首先我们依然采用最朴素的 暴力递归 来思考这道题目。
递归的准备
定义递归函数的功能： 使用 stickers 拼出 余下 的 目标字符串 所需的最小贴纸数量。
思考递归需要的参数： stickers 数组、target 目标串。
明确递归的边界条件： 目标字符串长度为 0 时，说明不再需要任何贴纸了，返回 0 。
思路
寻找相同类型子问题：
-
由于贴纸是无限的，因此使用一张贴纸后，剩下的目标字符串仍然可以当做一个新的目标字符串，问题的规模缩小了。而贴纸的类型不会发生改变。
-
直到目标字符串的长度减为 0 ，即递归到了 base case。
代码
public static int minStickers(String[] stickers, String target) {
int ans = process(stickers, target);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int process(String[] stickers, String target) {
// base case
if (target.length() == 0) {
return 0;
}
int min = Integer.MAX_VALUE;
// stickers 中的每个单词进行消除
for (String first : stickers) {
// 在 target 中删除 first 中含有的字母
// 剩下的结果存入 rest 中
String rest = minus(target, first);
// rest 与删除前 target 的长度不等说明 first 中有有效字符
// rest只有变化了才能调用递归，否则进入死循环
if (rest.length() != target.length()) {
// 求出first作为第一张，后续需要的最小贴纸数量
min = Math.min(min, process(stickers, rest));
}
}
// 若min变化了，说明此次递归是有效的拼接，贴纸张数+1
return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
public static String minus(String s1, String s2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[] count = new int[26];
for (char cha : str1) {
count[cha - 'a']++;
}
for (char cha : str2) {
count[cha - 'a']--;
}
StringBuilder builder = new StringBuilder();
// 还剩哪些字符，用 builder 全部拼起来
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
for (int j = 0; j < count[i]; j++) {
builder.append((char) (i + 'a'));
}
}
}
return builder.toString();
}
思考上面的递归过程发现，我们是 以贴纸为主线 ，去尝试每张贴纸能够 凑出目标字符 的哪些部分。因此，不论贴纸中是否存在可以消除目标字符串的字符，都会把 stickers 中的贴纸全部遍历一遍，而每张贴纸的遍历都需要调用 minus() 函数，再进行递归调用。造成了极大地浪费。
我们换一个思考方向，以目标字符串 target 为主线 ，去看那些贴纸能够满足要求，不满足要求的直接跳过，这样就减少了很多不必要的比较，达到了 剪枝 的目的。
另一方面，为了减少字符统计的调用频率。我们 提前做好字符统计 ，使用数组提前准备好，对于字符的操作转化为了数组的操作，提高效率。
优化代码
public static int minSticker(String[] stickers, String target) {
int N = stickers.length;
int[][] counts = new int[N][26];
// 将贴纸转化为二维数组，每一行存放的是一张贴纸的词频统计
for (int i = 0; i < N; i++) {
char[] str = stickers[i].toCharArray();
for (char cha : str) {
counts[i][cha - 'a']++;
}
}
int ans = process(counts, target);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int process(int[][] arrs, String t) {
if (t.length() == 0) {
return 0;
}
// 将目标字符 做字符统计 存入 tcounts[26] 中
char[] target = t.toCharArray();
int[] tcounts = new int[26];
for (char cha : target) {
tcounts[cha - 'a']++;
}
//
int N = arrs.length;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int[] arr = arrs[i];
// 谁能够做 target 第一个字符的贴纸
// 不能做 target 第一个字符的贴纸直接过滤
// 达到了剪枝的目的
if (arr[target[0] - 'a'] > 0) {
StringBuilder builder = new StringBuilder();
// 用了一张次贴纸后，目标串 target 还剩下什么了
for (int j = 0; j < 26; j++) {
if (tcounts[j] > 0) {
// 把这张贴纸上含有目标字符的其他字符也都去掉
int nums = tcounts[j] - arr[j];
for (int k = 0; k < nums; k++) {
builder.append((char) (j + 'a'));
}
}
}
String rest = builder.toString();
min = Math.min(min, process(arrs, rest));
}
}
return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
上面优化后的代码已经进行了大量的剪枝操作，那思考一下能否进一步优化呢？答案是 肯定的 。—— 加 缓存！
前面的题目我们都是用了 数组 作为 dp 表，那这道题目是否也能够用数组作为缓存表呢？好像不太行 ~
因为递归中 变化的量 是 字符串 ，而字符串的长度显然不容易确定范围。因此，我们这次采用 集合 的形式进行 记忆化搜索！HashMap 显然 最合适！
最终代码
public static int minSticker(String[] stickers, String target) {
int N = stickers.length;
int[][] counts = new int[N][26];
for (int i = 0; i < N; i++) {
char[] str = stickers[i].toCharArray();
for (char cha : str) {
counts[i][cha - 'a']++;
}
}
HashMap<String, Integer> dp = new HashMap<>();
dp.put("", 0);
int ans = process(counts, target, dp);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int process(int[][] arrs, String t, HashMap<String, Integer> dp) {
if (dp.containsKey(t)) {
return dp.get(t);
}
// 将目标字符 做字符统计 存入 tcounts[26] 中
char[] target = t.toCharArray();
int[] tcounts = new int[26];
for (char cha : target) {
tcounts[cha - 'a']++;
}
int N = arrs.length;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int[] arr = arrs[i];
// 谁能够做 target 第一个字符的贴纸
// 不能做 target 第一个字符的贴纸直接过滤
// 达到了剪枝的目的
if (arr[target[0] - 'a'] > 0) {
StringBuilder builder = new StringBuilder();
// 用了一张次贴纸后，目标串 target 还剩下什么了
for (int j = 0; j < 26; j++) {
if (tcounts[j] > 0) {
// 把这张贴纸上含有目标字符的其他字符也都去掉
int nums = tcounts[j] - arr[j];
for (int k = 0; k < nums; k++) {
builder.append((char) (j + 'a'));
}
}
}
String rest = builder.toString();
min = Math.min(min, process(arrs, rest, dp));
}
}
int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
dp.put(t, ans);
return ans;
}
使用 HashMap 记录已经找到过的剩余字符需要的最少贴纸数，若再次出现相同剩余字符序列后直接获取答案，达到了 记忆化搜索 的效果。
本文和上篇文章都从 暴力递归 入手，逐步进行优化，修改出了 动态规划 版本的最终代码。不同的是，本文题目并没有严格的表依赖结构，而是采用了 记忆化搜索（备忘录）进行替代，小伙伴们要加以区分哦 ~
~ 点赞 ~ 关注 ~ 不迷路 ~！！！文章来源：https://www.toymoban.com/news/detail-831504.html
------------- 往期回顾 -------------
【算法 - 动态规划】原来写出动态规划如此简单！
【堆 - 专题】“加强堆” 解决 TopK 问题！
AC 此题，链表无敌！！！文章来源地址https://www.toymoban.com/news/detail-831504.html
到了这里，关于【算法 - 动态规划】力扣 691. 贴纸拼词的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
