algorithm - 如何在这个递归解决方案中添加记忆来拼写单词

Question

我正在尝试解决https://leetcode.com/problems/stickers-to-spell-word/

我想出了下面的递归解决方案

class Solution {
    public int minStickers(String[] stickers, String target) {
        
        int[] arr = new int[26];
        
        for(int i = 0 ; i <26;++i) {
            arr[i]=0;
        }
        int len = target.length();
        
        for(int i = 0 ; i < len; ++i) {
            arr[target.charAt(i)-'a']++;
        }
        
        int lenS= stickers.length;
        Integer ans = cal( stickers, 0,arr, 0,len);
        if(ans==Integer.MAX_VALUE) {
            return -1;
        }
        return ans;
    }
    
    public int cal(String[] stickers, int pos, int[] arr, int count, int totalLen) {
        int[] mp = arr.clone();
        int curTotalLen=totalLen;
        int didChange=0;
        if(pos<stickers.length) {
            for(int i = 0 ; i < stickers[pos].length(); ++i) {
                
                 if(mp[stickers[pos].charAt(i)-'a'] > 0) {
                     mp[stickers[pos].charAt(i)-'a']--;
                         --curTotalLen;
       
                    didChange=1;
                 }
            }
            if(curTotalLen<=0) {

                return (count+didChange);
            }
            
            if(didChange==1) {

                return Math.min(cal(stickers,pos,mp,count+didChange,curTotalLen), 
                            cal(stickers,pos+1,arr,count,totalLen));
            }
          
            return  cal(stickers,pos+1,arr,count,totalLen);
        }
        return Integer.MAX_VALUE;
    }
}

我无法向这个递归解决方案添加记忆。我知道网上有很多针对这个问题的解决方案，但我想在我能想到的这个特定解决方案中添加moemoization。因此，我的解决方案所做的就是在每一步都对当前单词和下一个单词进行递归。如果当前单词不能减少目标中的字符数，那么它将不会为它递归，否则它将为它递归。（在我用尽所有的stcikers之前，它总是会递归下一个贴纸）

标签： algorithmrecursiondata-structuresdynamic-programming