LeetCode刷题：664. Strange Printer
原题链接：https://leetcode.com/problems/strange-printer/
There is a strange printer with the following two special requirements:
The printer can only print a sequence of the same character each time.
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:
输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:
输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示: 输入字符串的长度不会超过 100。
算法分析
如果字符串s只包含1个字符，那么只需要打印1次即可结束。
如果字符串s包含2个字符呢？如果两个字符相同，则只需要打印1次，如果两个字符不相同，则需要打印2次。
那么字符串s包含3个字符呢？
例如：s = "abc"，3个字符可拆分的情况如下所示
abc
/ \
a,bc ab,c
对于一个复杂的字符串s有很多种划分的方法，但是我们选择最简单的方法：
划分s的方法数 = min（turns one substring needed + turns the other needed）
怎么理解呢？
假设 s=“aba”，我们把s划分为“a，ba”
aba = "a" + "ba"-1 (aaa => aba 而不是 a => ab = aba)
为了避免重复计算，我们使用自下而上的动态编程实现了上述思想。
状态： state[i][j] turns needed to print s[i .. j] (both inclusive)
目标状态： state[0][n - 1] (n = s.length() - 1)
状态转换：
state[i][i] = 1;
如果满足条件： s[i] == s[i + 1]时，state[i][i + 1] = 1
如果满足条件： s[i] != s[i + 1]，state[i][i + 1] = 2
当 i <= k <= j - 1时，state[i][j] = min(state[i][k] + state[k + 1][j]) ，
请注意： 如果 s[i] 和 s[j] 相等, 则state[i][j] 必须要 -1
说明：
我们观察到在小部分上定义的状态有助于在大部分上定义的状态。
我们定义 j = i + dist ， 这使得问题变得简单一些。
例如：i = 2, dist = 3 for example,
state[2][5] = state[2][3] + state[4][5],
state[4][5] 必须在 state[2][5]之前先进行计算, 所以 i 必须保持递减
dist = |5 - 4| 必须在 dist = |5 - 2|之前先进行计算, 所以 dist 必须保持递减.
算法设计
public int strangePrinter(String s) {if (s == null || s.length() == 0) {return 0;}int n = s.length();int[][] state = new int[n][n];for (int i = 0; i < n; i++) {state[i][i] = 1;}for (int i = n - 1; i >= 0; i--) {for (int dist = 1; dist + i < n; dist++) {int j = dist + i;if (dist == 1) {state[i][j] = (s.charAt(i) == s.charAt(j)) ? 1 : 2;continue;}state[i][j] = Integer.MAX_VALUE;for (int k = i; k + 1 <= j; k++) {int tmp = state[i][k] + state[k + 1][j];state[i][j] = Math.min(state[i][j], tmp);}if (s.charAt(i) == s.charAt(j)) {state[i][j]--;}}}return state[0][n - 1];
}Accepted~
