664.strange-printer

• 题解
  
  

  class Solution {
    public int strangePrinter(String s) {
            if(s.length()==0)return 0;
            int n = s.length();
            int dp[][] = new int [n][n];
            // for(int i = 0 ; i < n ; i++ ) {  //当然这一步可以放在下面for循环里面
            //     dp[i][i] = 1 ;  //每一步都是打印一次 也就是染一次 最坏情况
            // }
            for(int j =0 ; j < n; j++ ) { //开始到结尾的截断字符串长度   //上面没有注释 则 j = 1
                for(int i = 0 ; i + j < n ; i++) { //从第一位开始dp
                    dp[i][i+j] = 1 + j;      //最坏情况 i + f(i,j):(j - i + 1 )
                    for(int k = i ; k < i + j ; k++) {
                        int sum = dp[i][k] + dp[k+1][i+j] ;
                        if(s.charAt(k)==s.charAt(i+j)) {  //直接被覆盖 例如 abaa  所以 后面两个aa可以一起覆盖
                            sum--;
                        }
                        dp[i][j+i] = Math.min(dp[i][i+j], sum);
                    }
                }
            }
            return dp[0][n-1];
        }
  }

  

  class Solution {
    public int strangePrinter(String s) {
            if(s.length()==0)return 0;
            int n = s.length();
            int f[][] = new int [n+1][n+1];
            for(int len = 1 ; len <= n ;len++) {
                for(int l = 0 ; l+len -1 < n ; l++) {
                    int r = l + len - 1;
                    f[l][r] = f[l+1][r] + 1 ;
                    for(int k = 1 +l ; k<=r ;k++) {
                        if(s.charAt(k)==s.charAt(l)) {
                            f[l][r] = Math.min(f[l][r],f[l][k-1]+f[k+1][r]);
                        }
                    }
                }
            }
            return f[0][n-1];
        }
  }

区间DP

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }
转移方程

dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j],dp_max[i][j])+sum(i,j);

dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j],dp_min[i][j])+sum(i,j);