题解 | #压缩字符串(二)#

import java.util.*;

/**
 * NC187 压缩字符串(二)
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param k int整型
     * @return int整型
     */
    public int compressString (String s, int k) {
        return solution(s, k);
    }

    /**
     * 动态规划
     *
     * dp[i][j]表示字符串前i个字符删除j个字符后的最小压缩长度  , j<=k&&j<=i
     * 
     * dp[0][0] = 0
     * 
     * same: 从第i个字符依次向左统计 与第i个字符相同的个数
     * diff: 从第i个字符依次向左统计 与第i个字符不同的个数(将被删除)
     * 
     * step 1
     * dp[i][j] = dp[i-1][j-1]  , j>0
     * step 2
     * dp[i][j] = Math.min(dp[i][j], dp[m-1][j-diff]+calculate(same))  , 0<m<=i && diff<=j
     * 
     * i:   0 1 2 3 4 5 6 7 8 9
     * s:     a a b a a a c c c
     * k=0  0 1 2 3 4 5 5 6 7 7
     * k=1    0 1 2 2 2 2 3 4 4
     * k=2      0 1 2 2 2 2 3 4
     * k=3        0 1 2 2 2 2 3
     * 
     * @param s
     * @param k
     * @return
     */
    private int solution(String s, int k){
        int n = s.length();

        int[][] dp = new int[n+1][k+1];

        // init
        for(int i=0; i<=n; i++){
            // >>1 防止溢出
            Arrays.fill(dp[i], Integer.MAX_VALUE>>1);
        }
        dp[0][0] = 0;

        for(int i=1; i<=n; i++){
            for(int j=0; j<=k&&j<=i; j++){
                if(j > 0){
                    dp[i][j] = dp[i-1][j-1];
                }
                // 从第i个字符依次向左统计 与第i个字符相同的个数
                int same = 0;
                // 从第i个字符依次向左统计 与第i个字符不同的个数
                int diff = 0;
                for(int m=i; 0<m&&diff<=j; m--){
                    if(s.charAt(m-1) == s.charAt(i-1)){
                        same++;
                        dp[i][j] = Math.min(dp[i][j], dp[m-1][j-diff]+calculate(same));
                    }else{
                        diff++;
                    }
                }
            }
        }

        return dp[n][k];
    }

    /**
     * 计算压缩后的长度
     * @param same 相同字符长度
     * @return
     */
    private int calculate(int same){
        if(same == 1){
            return 1;
        }
        if(same < 10){
            return 2;
        }
        if(same < 100){
            return 3;
        }
        return 4;
    }
}