动态规划——StickersToSpellWord

题目

**给定一个字符串str，给定一一个字符串类型的数组arr。
arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
返回需要至少多少张贴纸可以完成这个任务。
例子: str= “babac”，arr = {“ba”,“c”,“abcd”}
至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，含有2个a、2个b、1个c。是可以拼出str的。所以返回2。
提示：可变参数能少则少，可变参数越少，缓存结构的命中率越高**

package com.harrison.class13;

import java.util.HashMap;

public class Code07_StickersToSpellWord {
    // 伪代码
//    public static int getMinStickers(String rest,String[] arr) {
//        // 加过滤 保证所有贴纸里的字符能够覆盖目标字符串
//    }
//    
//    public static int minStickers(String rest,String[] arr) {
//        if(rest.equals("")) {
//            return 0;
//        }
//        int next=0;
//        for(String first:arr) {
//            rest-first -> nextRest;
//            int cur=minStickers(nextRest, arr);
//            next=Math.min(next, cur);
//        }
//        return next+1;
//    }
    
    public static int minStickers1(String[] stickers,String target) {
        int n=stickers.length;
        int[][] map=new int[n][26];
        for(int i=0; i<n; i++) {
            char[] str=stickers[i].toCharArray();
            for(char c:str) {
                map[i][c-'a']++;
            }
        }
        HashMap<String, Integer> dp=new HashMap<>();
        dp.put("", 0);
        return process1(dp, map, target);
    }
    
    // dp 傻缓存，如果rest已经算过了，直接返回dp中的值
    // 0...N中每一个字符串所含字符的词频统计
    // 返回值是-1，map中的贴纸无论如何都无法搞定rest
    public static int process1(HashMap<String, Integer> dp,int[][] map,String rest) {
        if(dp.containsKey(rest)) {
            return dp.get(rest);
        }
        // 搞定rest，使用最少的贴纸数量
        int ans=Integer.MAX_VALUE;
        // n种贴纸
        int n=map.length;
        // tmap替代rest
        int[] tmap=new int[26];
        char[] target=rest.toCharArray();
        for(char c:target) {
            tmap[c-'a']++;
        }
        // map-tmap
        for(int i=0; i<n; i++) {// 枚举当前第一张贴纸是谁
            // 小贪心 确保贴纸中至少含有目标字符串中的一种字符才进行尝试
            // 目标字符串中0位置的字符，当前贴纸是否有
            if(map[i][target[0]-'a']==0) {
                continue;
            }
            StringBuilder sb=new StringBuilder();
            // i 当前来到的第一张贴纸
            // j 枚举a~z字符
            for(int j=0; j<26; j++) {
                if(tmap[j]>0) {// j这个字符是target需要的（要搞定的字符串里有这个字符）
                    for(int k=0; k<Math.max(0, tmap[j]-map[i][j]); k++) {
                        sb.append((char)('a'+j));
                    }
                }
            }
            // 经历上面的for循环后，目标字符串减去了第一张贴纸(i)里的字符，
            // 剩余的字符在sb里面
            String s=sb.toString();
            int tmp=process1(dp, map, s);
            if(tmp!=-1) {
                ans=Math.min(ans, tmp+1);
            }
        }
        dp.put(rest, ans==Integer.MAX_VALUE?-1:ans);
        return dp.get(rest);
    }
    
    public static void main(String[] args) {
        String[] arr= {"aaaa","bbaa","ccddd"};
        String str="abcccccdddddbbbaaaaa";
        System.out.println(minStickers1(arr,str));
    }
}