664 Strange Printer

664. Strange Printer

1. Question

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.

2. Implementation

(1) DP (区间DP)

思想: 题目说一台打印机可以一次打印一序列相同的字母，问我们给定一个string，我们可以通过打印机用最少多少次得到这个string。

我们可以用动态规划dp[i][j]表示在[i...j]的区间里，得到s[i....j]所需要的最少打印次数，难点在于找到状态转移方程。通过观察发现，由于这台打印机的特性，它会打印若干个相同字母，然后我们可以在打印完的这段字母串里，打印别的字母覆盖先前的字符，比如对于aba, 我们先打"aaa", 然后在第二个a的位置上打印b，这样只需要两步就可以得到aba。 当然我们也可以先打印bbb，然后分别在第一个b和第3个b的位置上各打印一个a，这就需要3步。所以关键的一点是，对于s[i], 我们在[i + 1,j]的区间里，我们找到一个字符s[k]和s[i]相等，将[i + 1, j]拆分成两个区间[i + 1, k - 1], [k, j]，将两个区间的dp值相加和dp[i][j]比较，取较小值

则 dp[i][j] = Math.min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]) if s[i] == s[k] and i + 1 <= k <= j

显然对于dp[i][j]的初始化，dp[i][j] = 1 当i== j，因为相同位置d额同一个字符只需要打印一次，否则dp[i][j] = 1 + dp[i + 1][j]

class Solution {
    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int n = s.length();
        int[][] dp = new int[n][n];

        for (int len = 1; len <= n; len++) {
            for (int start = 0; start < n - len + 1; start++) {
                int end = start + len - 1;

                dp[start][end] = start == end ? 1 : 1 + dp[start + 1][end];

                for (int mid = start + 1; mid <= end; mid++) {
                    if (s.charAt(start) == s.charAt(mid)) {
                        dp[start][end] = Math.min(dp[start][end], dp[start + 1][mid - 1] + dp[mid][end]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

3. Time & Space Compleixity

DP:时间复杂度O(n^3), 空间复杂度O(n^2)