题目描述

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

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

给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

样例

输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。

输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示

• 输入字符串的长度不会超过 100。

算法

(动态规划) $O(n^3)$

1. 状态 $f(i,j)$ 表示打印区间 [i, j] 所需要的最少步数。
2. 初始值 $f(i, i) = 1$，$f(i,i - 1) = 0$；
3. 转移条件，每次扩展到新的长度时，[i, j] 区间的首字符尤为重要，因为区间 [i, j] 的某个最优解一定是第一次将首字符全部写满区间 [i, j]；
4. 接下来，假设区间中最右侧仍保留着第一次写的首字符的位置为 k。若 $k$ 就是 $i$，则表示除了首字符之外，区间内其余所有字符都被重新覆盖过，则可以给出的转移为 $f(i,j) = min(f(i, j), 1 + f(i + 1, j))$；若 $k > i$，则可以转移 $f(i,j) = min(f(i, j), f(i, k - 1) + f(k + 1, j))$，可以分为两段区间求和的原因是，区间 [i, k - 1] 仍然可以用首字符按照以上规则进行划分，且不必考虑 $k$ 位置的字符，所以才可以用求出的子结果，不影响整个优化过程；区间 [k + 1, j] 则显然是直接利用求出的子结果。
5. 最终答案为 $f(0, n - 1)$。

时间复杂度

• 状态数为 $O(n^2)$，转移数为 $O(n)$，故总时间复杂度为 $O(n^3)$。

C++ 代码

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        if (n == 0)
            return 0;
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        for (int i = 0; i <= n; i++) {
            f[i][i] = 1;
            if (i > 0)
                f[i][i - 1] = 0;
        }

        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                f[i][j] = 1 + f[i + 1][j];
                for (int k = i + 1; k <= j; k++)
                    if (s[i] == s[k])
                        f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j]);
            }

        return f[0][n - 1];
    }
};