一、题目

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

点击查看原题

二、思路

动态规划
对于字符类的题目，动态规划套路大致一致，使用dp[i][j]，i和j分别为字符串片段的起始位置和终止位置，dp[i][j]代表该片段需要的最少打印次数。
如果i==j，那么dp[i][j]等于1
当i != j时：
利用连续打印的性质，对于新加入的s[j]，如果s[i, j-1]中有相等的字符，那么分别打印s[i, k]和s[k+1, j]
如果s[i]和s[j]字符相等，那就相当于打印一次s[i, j-1]
整理得到状态转移方程：

三、代码

class Solution {
    public int strangePrinter(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = dp.length - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < dp.length; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i][j-1];
                } else {
                    int val = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        val = Math.min(val, dp[i][k] + dp[k+1][j]);
                    }
                    dp[i][j] = val;
                }
            }
        }
        for (int[] i : dp) {
            System.out.println(Arrays.toString(i));
        }
        return dp[0][dp.length - 1];
    }
}

时间复杂度为O(n)，空间复杂度为O(n)。