【算法题】LeetCode691、贴纸拼词（剪枝+记忆化搜索）

hello hello，好久不见。

今天我们来看一道算法题：LeetCode691 贴纸拼词。这是一道hard难度的题，还是很有难度的。

题意：给你一堆贴纸stickers，和一个英文单词。每一种贴纸都有无限张，并且每一张贴纸能剪切成一个个的字母。

现在问你，如何用最少的贴纸，组成这个英文单词？请返回最少贴纸张数。

分析：动态规划刷的多的同学，应该能够反应过来，这是一道类似于背包问题的dp题。

尝试思路是：第一张贴纸，我用、1张、2张……，这样去尝试；第二张贴纸，我用、1张、2张……。一直尝试到最后一张贴纸。

只要英文单词target变为空字符串，那么我们就尝试成功了，这就是其中一种尝试方法。

文章目录

1、递归版本

代码框架：

// 主函数publicintminStickers(String[] stickers,String target){if(stickers ==null|| stickers.length ==0|| target ==null|| target.length()==0){return0;}int ans =process(stickers, target);// 调用递归函数return ans ==Integer.MAX_VALUE ?-1: ans;}// 递归函数：返回 拼target字符串，最少需要多少贴纸？publicintprocess(String[] stickers,String target){}

那么现在我们只需要填好递归函数，这个代码就算写完了。

根据分析，只要target变为空字符串，那么我们就可以直接返回了。所以递归结束条件：

if (target.length() == 0) return 0

;

接下来就是尝试，用第一张贴纸去试试，然后调用递归函数；用第二张贴纸去试试，然后调用递归函数……

// 递归函数：返回 拼target字符串，最少需要多少贴纸？publicstaticintprocess(String[] stickers,String target){if(target.length()==0){return0;}int min =Integer.MAX_VALUE;// for(String first : stickers){// 用first字符串去试试，能消除target多少个字母String rest =minus(target, first);// 消除一定的字符// 如果first字符串，一个也没消除掉，// 就不用调用后续递归函数，以免造成死递归if(rest.length()!= target.length()){// 确实是first消除了一些字符后，调用后续过程
            min =Math.min(min,process(stickers, rest));}}// 返回结果之前，要判断min是不是Integer.MAX_VALUE// 不然直接+1，会造成溢出。return min ==Integer.MAX_VALUE ? min : min +1;// 加上当前这一个位置的帖纸}// 根据str字符串，消除在target中的字符publicStringminus(String target,String sticker){int[] count =newint[26];for(char ch : target.toCharArray()){
        count[ch -'a']++;}for(char ch : sticker.toCharArray()){
        count[ch -'a']--;}StringBuilder sb =newStringBuilder();for(int i =0; i <26; i++){while(count[i]-->0){
            sb.append((char)(i +'a'));}}return sb.toString();}

这个递归版本，在LeetCode中，能够一部分用例，其他用例没通过的原因就是，这个递归函数调用了很多重复计算的子过程。所以需要在递归版本的基础之上，再次进行优化。

2、剪枝版本

所谓剪枝，可以这么理解，实际在递归调用的时候，递归调用的展开图如下：

也就是说，在某一个递归调用的过程中，额外加的if语句不成立，导致递归函数没必要调用后续的过程，直接返回上一层调用，这样的行为就称为剪枝。

那么这道题，应该如何剪枝？举个例子：

假设 target = “hello”，按照上面的递归版本的代码会这样调用：

for() {

​ 删除第一个h，递归调用后续；

​ 删除第二个e，递归调用后续；

​ 删除第三个l，递归调用后续；

​ ……

}

你会发现，在这一个for循环中，居然枚举了删除每一个字母的过程，看上去好像并没有什么问题。但仔细想想，有必要吗？

其实并没有必要，比如说 这一层递归函数消除h，和下一层递归函数消除h，这两个并没有什么本质上的区别，其目的就是为了使target变为空字符串。如下图所示：

代码如下，稍微有些改动，以前的帖纸是以字符串数组来存储的，我们需要稍微调整一下，用二维数组存储，一行表示一种贴纸，一列表示这种贴纸中的字母数量，也就是词频统计嘛。

// 剪枝之后的递归版本publicintminStickers(String[] stickers,String target){if(stickers ==null|| stickers.length ==0|| target ==null|| target.length()==0){return0;}intN= stickers.length;int[][] stickers2 =newint[N][26];// 用二维表存储所有的帖纸for(int i =0; i <N; i++){for(char ch : stickers[i].toCharArray()){
            stickers2[i][ch -'a']++;}}int ans =process2(stickers2, target);return ans ==Integer.MAX_VALUE ?-1: ans;}// 递归函数--剪枝版本publicintprocess2(int[][] stickers,String target){if(target.length()==0){return0;}int min =Integer.MAX_VALUE;int[] count =newint[26];for(char ch : target.toCharArray()){
        count[ch -'a']++;}char firstCh = target.charAt(0);// target第一个字母for(int i =0; i < stickers.length; i++){// 剪枝优化，当前递归，只需要解决target的第一个字符即可，后续的不用管，交给其他调用if(stickers[i][firstCh -'a']>0){StringBuilder sb =newStringBuilder();// 消除target中的字母for(int j =0; j <26; j++){int nums = count[j]- stickers[i][j];// target 减掉 帖纸相应的字符for(int k =0; k < nums; k++){
                    sb.append((char)(j +'a'));}}String rest = sb.toString();// 生成rest字符串
            min =Math.min(min,process2(stickers, rest));}}return min ==Integer.MAX_VALUE ? min : min +1;}

剪枝版本的代码虽然做到了一定的优化，但是在LeetCode上，还是会超时。这就需要再优化成动态规划版本了。

3、动态规划版本

从递归版本的代码可以看出，递归函数process在调用的过程中，形参只有一个target在变化，所以在我们以前的惯性思维中，只有一个可变参数，那我搞一维数组就能搞定了。

但是，用一维数组在这道题能行的通吗？好像并不可以。为什么？

原因在于如果用一维数组，这个数组我应该开辟多大的空间？这个空间的大小是根据target的变化范围来定的。而target的变化范围并不是很好计算。那么这道题用一维数组，不太可行。

只能用记忆化搜索。

既然可变参数是一个字符串类型，那么用哈希表存储，就能解决这个问题了。改记忆化搜索版本，也比较简单，在递归函数中，随身带着这个哈希表即可，其他的代码不用改，还是用剪枝版本的即可。

// 记忆化搜索版本--无法根据递归版本解出具体的dp表，因为递归函数的可变参数，无法计算出具体的参数范围// 又或者说，这个具体的参数范围大到已经没必要进行优化了，所有就用哈希表来搞记忆化搜索即可publicstaticintminStickers(String[] stickers,String target){if(stickers ==null|| stickers.length ==0|| target ==null|| target.length()==0){return0;}intN= stickers.length;int[][] stickers2 =newint[N][26];for(int i =0; i <N; i++){for(char ch : stickers[i].toCharArray()){
            stickers2[i][ch -'a']++;}}// 哈希表存储HashMap<String,Integer> dp =newHashMap<>();
    dp.put("",0);// base case// 只需递归过程中，带着哈希表即可int ans =process3(stickers2, target, dp);return ans ==Integer.MAX_VALUE?-1: ans;}publicstaticintprocess3(int[][] stickers,String target,HashMap<String,Integer> dp){if(dp.containsKey(target)){// 表中有这个数据，就直接用即可return dp.get(target);}int[] count =newint[26];for(char ch : target.toCharArray()){
        count[ch -'a']++;}int min =Integer.MAX_VALUE;for(int i =0; i < stickers.length; i++){// 只递归调用 target字符串出现的第一个字符的情况if(stickers[i][target.charAt(0)-'a']>0){// 剪枝StringBuilder sb =newStringBuilder();for(int j =0; j <26; j++){int nums = count[j]- stickers[i][j];// target 减去 帖纸的字符个数for(int k =0; k < nums; k++){
                    sb.append((char)(j +'a'));}}String rest = sb.toString();
            min =Math.min(min,process3(stickers, rest, dp));}}// 结算min，在返回min时，必须提前将min存储在哈希表中，后续可能会被使用
    min = min ==Integer.MAX_VALUE? min : min +1;
    dp.put(target, min);return min;}

好啦，以上全部就是这道题的思路。重要的是理解了递归调用过程，那么这道题就迎刃而解了。

那我们下期再见吧！！！