664.奇怪的打印机

题目描述：

image.png

解：

区间DP
状态转移方程：

  • 只打印left这个位置： f[l][r] = f[l+1][r] + 1
  • 打印left到k(s[l] = s[k]) : f[l][r] = f[l][k-1] + f[k+1][r]

因为此时只保证了 l 和 k 位置字符相同，并不保证其中没有其他字符，所以应该取min值
区间DP一般就是枚举长度+枚举左端点+枚举分割点3重循环，复杂度664.奇怪的打印机 - 图2

  1. class Solution {
  2.     public int strangePrinter(String s) {
  3.         StringBuilder sb = new StringBuilder();
  4.         for(int i=0; i<s.length(); ) {
  5.             char c = s.charAt(i);
  6.             sb.append(c);
  7.             i++;
  8.             while (i < s.length() && s.charAt(i) == c) {
  9.                 i++;
  10.             }
  11.         } //删除重复字符，减少dp匹配次数。
  12.         s = sb.toString();
  13.         int n = s.length();
  14.         int[][] f = new int[n+1][n+1];
  15.         for(int len = 1; len<=n; len++) {  //枚举长度
  16.             for(int l = 0; l+len-1 < n; l++) { //枚举左端点
  17.                 int r = l + len - 1;
  18.                 f[l][r] = f[l+1][r] + 1;  //到左端点处
  19.                 for(int k = l+1; k<=r; k++) { //枚举分割点
  20.                     if(s.charAt(l) == s.charAt(k)) {
  21.                         f[l][r] = Math.min(f[l][r], f[l][k-1]+f[k+1][r]);
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         return f[0][n-1];
  27.     }
  28. }