输入：codes = ["a","ba","abab","b"] str = "bababbaababa"
输出：5
解释：编码的最好方式是(“b”，“abab”, “ba” ,“abab”,“a”)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3

二、解题思路

1. 定义状态

​ 设dp[i]表示字符串前i个字符组成的字符串最优码长，i从1开始计数，那么我们最终要求出的是dp[str.length]即为字符串str的最优码长;

​ 我们假设k <= i,假设字符串i的后k个字符串与编码相匹配，则有dp[i] = dp[i - k] + 1 ，当然k值可能有多个（多个编码匹配），我们取最小花费那个。

2. 定义状态转移方程

当k <= j并且字符串后k个字符组成字符串与编码匹配时, k为编码集中编码长度组成的集合，有

​ $$dp[i]=min(dp[i-k]+1),$$

3. 初始化

​ 当 i = 1时，有$$dp[1]=1$$

4. 计算方式

​ 自左向右计算

三、代码实现

/**
 * 最优编码数量
 *
 *  @author hh
 *  @date 2021-5-20 21:48
 */
public class OptimumCode {

    public int optimumCode(String[] codes,String str,String[] trace){
        int[] dp = new int[str.length() + 1];
        //初始化dp[1] = 1
        dp[1] = 1;
        for(int i = 1; i <= str.length(); i++){
            dp[i] = Integer.MAX_VALUE;
            for(String bizCode : codes){
                if(bizCode.length() > i){
                    continue;
                }
                int temp = dp[i - bizCode.length()] + 1;
                if(str.substring(i - bizCode.length(),i).equals(bizCode) && dp[i] > temp){
                    dp[i] = temp;
                    trace[i] = bizCode;
                }
            }
        }
        return dp[str.length()];
    }

    public void print(String[] trace,int index){
        Stack<String> stringStack = new Stack<>();
        while (index >= 1){
            stringStack.push(trace[index]);
            index -= trace[index].length();
        }
        System.out.print("最优编码为：");
        while (!stringStack.isEmpty()){
            if(stringStack.size() == 1){
                System.out.print(stringStack.pop());
            }else{
                System.out.print(stringStack.pop() + ",");
            }
        }
    }

    public static void main(String[] args){
        String[] codes = new String[]{"a","ba","abab","b"};
        String str = "bababbaababa";
        String[] trace = new String[str.length() + 1];
        OptimumCode optimumCode = new OptimumCode();
        System.out.println("最优编码长度：" +  optimumCode.optimumCode(codes,str,trace));
        optimumCode.print(trace,str.length());
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">