1
class Solution {
2

3
  public int strangePrinter(String s) {
4
    if (s.equals("")) return 0;
5
    int len = s.length();
6
    int[][] dp = new int[len][len];
7
    for (int i = 0; i < len; i++) dp[i][i] = 1;
8
    for (int l = 2; l <= len; l++) {
9
      for (int i = 0; i < len && l + i - 1 < len; i++) {
10
        int j = l + i - 1;
11
        dp[i][j] = dp[i][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
12
        for (int k = i + 1; k < j; k++) {
13
          if (s.charAt(k) == s.charAt(j)) {
14
            dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k][j - 1]);
15
          }
16
        }
17
      }
18
    }
19
    return dp[0][len - 1];
20
  }
21
}