Problem
1. 题目简述
有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例1:
Input: s = “aaabbb”
Output: 2
Explanation: Print “aaa” first and then print “bbb”.
要求：
1 <= s.length <= 100
s只有小写字母
2. 算法思路
Dynamic Programming
这道题目个人认为比较特殊，它是一个求最小值的问题，有点像dp，但是好像又和dp没什么关系，难以找出表达式。因此需要多复习，想想其状态转移方程的表示方法。
我们可以注意一下，对于任意一个子字符串s[i, j]，它的最差的打印方式不外乎就是一个个字符去打印，那么，次数最多就是 j - i + 1 次。如何进行优化呢？
我们发现，如果s[i] == s[j]，那么在最优解的时候，打印i的时候一定可以把j也附带着打印出来，反正中间的部分可以再被覆盖嘛，无所谓的。所以我们令dp[i][j]表示s[i, j]的打印最优解，此时dp[i][j] = dp[i][j - 1]。
如果s[i] ≠ s[j]，那么也就是说s[i]和s[j]的打印一定是两次独立的打印，那么具体是什么时候，在哪打印呢？我们不清楚。所以对于s[i, j]这个字符串来说，遍历i到j之间所有的位置k作为“分割线”，通过dp[i][k] + dp[k + 1][j]的最小值，也就是整个s[i, j]的最小值（最优打印方法），至于具体怎么打印的，谁在前，谁在后，没有影响的。
注意：在我们找到了某个s[i, j]的最优打印次数后，s[i][j]的最优打印方法已经确定了，但对于任意一个包含s[i, j]的字符串来说，并不表示s[i, j]的最优打印解，也是它们最优打印解的子集！！！还是要去进行dp计算的！！！
3. 解法
Dynamic Programming bottom-up
1 |
|