题目描述

There is a strange printer with the following two special requirements:

1. The printer can only print a sequence of the same character each time.
2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Hint: Length of the given string will not exceed 100.

题意：有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印同一个字符序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

算法1

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

题解：这种题目一般可以使用区间DP来解决。

-状态表示：dp[i][j]表示s[i:j]最少需要打印多少次。

-状态初始化：dp[i][i] = 1,其余初始化为0。

-状态转移：首先考虑初始化将dp[i][j] = dp[i][i] + dp[i + 1][j]，代表s[i]单独打印。

考虑所有的i < k < j，将区间s[i:j]拆分成s[i:k]和s[k + 1:j]两个部分。

如果s[i] == s[k]，说明区间s[k]可以和s[i]同时打印，所以s[i][k] = s[i][k - 1]，那么dp[i][j] = min(dp[i][j],dp[i][k - 1] + dp[k + 1][j])。

最后考虑如果s[i] = s[j]，说明s[j]可以和s[i]一起打印，那么dp[i][j] = min(dp[i][j],dp[i + 1][j])

最后结果为dp[0][n - 1]

C++ 代码

    int strangePrinter(string s) {
        int n = s.length();
        if(n == 0) return 0;
        int dp[n][n];
        memset(dp,0,n * n * sizeof(int));
        for(int i = 0 ; i < n ;i ++) dp[i][i] = 1;
        for(int len = 1; len < n; len ++)
        {
            for(int i = 0 ; i + len < n;i ++)
            {
                int j = i + len;
                dp[i][j] = 1 + dp[i + 1][j];
                for(int k = i + 1;k < j ; k ++)
                    if(s[i] == s[k])
                        dp[i][j] = min(dp[i][j],dp[i][k - 1] + dp[k + 1][j]);
                if(s[i] == s[j]) 
                    dp[i][j] = min(dp[i][j],dp[i + 1][j]);
            }
        }
        return dp[0][n - 1];
    }