https://leetcode.com/problems/strange-printer
http://www.cnblogs.com/grandyang/p/8319913.html
X. https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-664-strange-printer/
理解了上面的DP的方法，那么也可以用递归的形式来写，记忆数组memo就相当于dp数组，整个思路完全一样，
https://leetcode.com/problems/strange-printer/discuss/106794/One-suggestion-for-all-solutions
https://discuss.leetcode.com/topic/100137/java-solution-dp
So we have
https://leetcode.com/problems/strange-printer/discuss/152758/Clear-Logical-Thinking-with-Code
X. Proof
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.
http://www.cnblogs.com/grandyang/p/8319913.html
这道题说有一种奇怪的打印机每次只能打印一排相同的字符，然后可以在任意起点和终点位置之间打印新的字符，用来覆盖原有的字符。现在给了我们一个新的字符串，问我们需要几次可以正确的打印出来。题目中给了两个非常简单的例子，主要是帮助我们理解的。博主最开始想的方法是一种类似贪婪算法，先是找出出现次数最多的字符，然后算需要多少次变换能将所有其他字符都变成那个出现最多次的字符，结果fail了。然后又试了一种类似剥洋葱的方法，从首尾都分别找连续相同的字符，如果首尾字符相同，则两部分一起移去，否则就移去连续相同个数多的子序列，这种基于贪婪算法的解法还是fail了，所以这道题是典型的只能动态规划Dynamic Programming，而不能用贪婪算法Greedy Algorithm的题。这道题的解题思路跟之前那道Remove Boxes很相似，博主在那个帖子中做了详细的讲解，是根据fun4leetcode大神的帖子写的，大神的思路对解这道题也相当有帮助。其实这道题并没有之前那道Remove Boxes难，移除盒子的题有隐含的条件需要加到重现关系中，大大地增加了题目的难度，非常地难想出来，这道题没有隐含条件都是个Hard题，那道题妥妥应该是Super Hard。
好，话不多说，来分析这道题吧。思考的线索和思路很重要，不理解核心精髓，当背题侠是没用的，稍微变个形式又不会了，博主就经常是这样的-.-!!!。既然说了要用DP来做，先整个二维dp数组呗，其中dp[i][j]表示打印出字符串[i, j]范围内字符的最小步数，难点就是找递推公式啦。遇到乍看去没啥思路的题，博主一般会先从简单的例子开始，看能不能分析出规律，从而找到解题的线索。首先如果只有一个字符，比如字符串是"a"的话，那么直接一次打印出来就行了。如果字符串是"ab"的话，那么我们要么先打印出"aa"，再改成"ab"，或者先打印出"bb"，再改成"ab"。同理，如果字符串是"abc"的话，就需要三次打印。那么一个很明显的特征是，如果没有重复的字符，打印的次数就是字符的个数。燃鹅这题的难点就是要处理有相同字符的情况，比如字符串是"aba"的时候，我们先打"aaa"的话，两步就搞定了，如果先打"bbb"的话，就需要三步。我们再来看一个字符串"abcb"，我们知道需要需要三步，我们看如果把这个字符串分成两个部分"a"和"bcb"，它们分别的步数是1和2，加起来的3是整个的步数。而对于字符串"abba"，如果分成"a"和"bba"，它们分别的步数也是1和2，但是总步数却是2。这是因为分出的"a"和"bba"中的最后一个字符相同。对于字符串"abbac"，因为位置0上的a和位置3上的a相同，那么整个字符串的步数相当于"bb"和"ac"的步数之和，为3。那么分析到这，是不是有点眉目了？我们关心的是字符相等的地方，对于[i, j]范围的字符，我们从i+1位置上的字符开始遍历到j，如果和i位置上的字符相等，我们就以此位置为界，将[i+1, j]范围内的字符拆为两个部分，将二者的dp值加起来，和原dp值相比，取较小的那个。所以我们的递推式如下:
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j] (s[k] == s[i] and i + 1 <= k <= j)
要注意一些初始化的值，dp[i][i]是1，因为一个字符嘛，打印1次，还是就是在遍历k之前，dp[i][j]初始化为 1 + dp[i + 1][j]，为啥呢，可以看成在[i + 1, j]的范围上多加了一个s[i]字符，最坏的情况就是加上的是一个不曾出现过的字符，步数顶多加1步，注意我们的i是从后往前遍历的，当然你可以从前往后遍历，参数对应好就行了
int strangePrinter(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { dp[i][j] = (i == j) ? 1 : (1 + dp[i + 1][j]); for (int k = i + 1; k <= j; ++k) { if (s[k] == s[i]) dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]); } } } return (n == 0) ? 0 : dp[0][n - 1]; }
(动态规划) O(n3)O(n3)
状态 f(i,j)f(i,j) 表示打印区间 [i, j] 所需要的最少步数。
初始值 f(i,i)=1f(i,i)=1，f(i,i−1)=0f(i,i−1)=0；
转移条件，每次扩展到新的长度时，[i, j] 区间的首字符尤为重要，因为区间 [i, j] 的某个最优解一定是第一次将首字符全部写满区间 [i, j]；
接下来，假设区间中最右侧仍保留着第一次写的首字符的位置为 k。若 k == i，则表示除了首字符之外，区间内其余所有字符都被重新覆盖过，则可以给出的转移为 f(i,j)=min(f(i,j),1+f(i+1,j))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))f(i,j)=min(f(i,j),f(i,k−1)+f(k+1,j))，可以分为两段区间求和的原因是，区间 [i, k - 1] 仍然可以用首字符按照以上规则进行划分，且不必考虑 k 位置的字符，所以才可以用求出的子结果，不影响整个优化过程；区间 [k + 1, j] 则显然是直接利用求出的子结果。
最终答案为 f(0,n−1)f(0,n−1)。
时间复杂度
状态数为 O(n2)O(n2)，转移数为 O(n)O(n)，故总时间复杂度为 O(n3)O(n3)。
Time Complexity:
O(n^3)
Space Complexity:
O(n^2)
public int strangePrinter(String s) {
int l = s.length();
t_ = new int[l][l];
return turn(s.toCharArray(), 0, l - 1);
}
// Minimal turns to print s[i] to s[j]
private int turn(char[] s, int i, int j) {
// Empty string
if (i > j) return 0;
// Solved
if (t_[i][j] > 0) return t_[i][j];
// Default behavior, print s[i] to s[j-1] and print s[j]
int ans = turn(s, i, j-1) + 1;
for (int k = i; k < j; ++k)
if (s[k] == s[j])
ans = Math.min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));
return t_[i][j] = ans;
}
private int[][] t_;
}
|
对于动态规划问题，最重要的考虑的就是寻找状态转移方程，而状态转移方程又来自于子问题的分析。也就是需要把一个大问题分解为若干个子问题，每个子问题都可以有解，并且子问题的解又来自其他子问题的解。
int strangePrinter(string s) { int n = s.size(); vector<vector<int>> memo(n, vector<int>(n, 0)); return helper(s, 0, n - 1, memo); } int helper(string s, int i, int j, vector<vector<int>>& memo) { if (i > j) return 0; if (memo[i][j]) return memo[i][j]; memo[i][j] = helper(s, i + 1, j, memo) + 1; for (int k = i + 1; k <= j; ++k) { if (s[k] == s[i]) { memo[i][j] = min(memo[i][j], helper(s, i + 1, k - 1, memo) + helper(s, k, j, memo)); } } return memo[i][j]; }
I suggest to do this treatment, before go directly DP.
Shorten the original string, like reduce
aaabbb to ab.
The same consecutive characters won't change the result and this really help improve the efficiency.
Besides, in python, it takes only 1 line to do it:
s = ''.join(a for a, b in zip(s, '#' + s) if a != b)
or use regex
s = re.sub(r'(.)\1*', r'\1', s)
It is natural to consider letting
dp(i, j) be the answer for printing S[i], S[i+1], ..., S[j], but proceeding from here is difficult. We need the following sequence of deductions:- Whatever turn creates the final print of
S[i]might as well be the first turn, and also there might as well only be one print, since any later prints on interval[i, k]could just be on[i+1, k]. - Say the first print is on
[i, k]. We can assumeS[i] == S[k], because if it wasn't, we could print up to the last occurrence ofS[i]in[i, k]for the same result. - When correctly printing everything in
[i, k](withS[i] == S[k]), it will take the same amount of steps as correctly printing everything in[i, k-1]. This is because ifS[i]andS[k]get completed in separate steps, we might as well print them first in one step instead.
Algorithm
With the above deductions, the algorithm is straightforward.
To compute a recursion for
dp(i, j), for every i <= k <= j with S[i] == S[k], we have some candidate answer dp(i, k-1) + dp(k+1, j), and we take the minimum of these candidates. Of course, when k = i, the candidate is just 1 + dp(i+1, j).
To avoid repeating work, we memoize our intermediate answers
dp(i, j).- Time Complexity: where is the length of
s. For each of possible states representing a subarray ofs, we perform work iterating throughk. - Space Complexity: , the size of our
memo.
Let
dp(i, j) be the number of turns needed to print S[i:j+1].
Note that whichever turn creates the final print of S[i], might as well be the first turn, and also there might as well only be one print, since any later prints on interval [i, k] could just be on [i+1, k].
So suppose our first print was on [i, k]. We only need to consider prints where S[i] == S[k], because we could instead take our first turn by printing up to the last printed index where S[k] == S[i] to get the same result.
Then, when trying to complete the printing of interval [i, k] (with S[i] == S[k]), the job will take the same number of turns as painting [i, k-1]. This is because it is always at least as good to print [i, k] first in one turn rather than separately.
Also, we would need to complete [k+1, j]. So in total, our candidate answer is dp(i, k-1) + dp(k+1, j). Of course, when k == i, our candidate is 1 + dp(i+1, j): we paint S[i] in one turn, then paint the rest in dp(i+1, j) turns.
int[][] memo;
public int strangePrinter(String s) {
int N = s.length();
memo = new int[N][N];
return dp(s, 0, N - 1);
}
public int dp(String s, int i, int j) {
if (i > j)
return 0;
if (memo[i][j] == 0) {
int ans = dp(s, i + 1, j) + 1;
for (int k = i + 1; k <= j; ++k)
if (s.charAt(k) == s.charAt(i))
ans = Math.min(ans, dp(s, i, k - 1) + dp(s, k + 1, j));
memo[i][j] = ans;
}
return memo[i][j];
what the algorithms doing is
- it sets basic print to 1 per character
2.it sets [i][i] to 1, which means any substring start from i to i (basically a single char). - it add 1 to the printing needs as soon as there is extra char. after [i]loop and [j]loop.
- then it checks substring between [i] and [j] which is [k]
then it minus the printing needs as soon as it found a same char. (it uses the data from last run so basically it is checking one char per turn) - [i] is decreasing. [j] is increasing. which means it is checking from the middle with k running between i and j.
- it uses the Math.min to check wether [i][j] value (which can be lower if there is alot of character common from start to end) and take the lower value.
- return the substring [0] [n-1] , i.e. the whole string value back.
When i saw the problem, my instincts told me it is recursive pattern. This is clever execution of recursion into iteration and use keys avoid repetitive calculations.
public int strangePrinter(String s) {
int n = s.length();
if (n == 0) return 0;
int[][] dp = new int[101][101];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
dp[j][j + i] = i + 1;
for (int k = j + 1; k <= j + i; k++) {
int temp = dp[j][k - 1] + dp[k][j + i];
if (s.charAt(k - 1) == s.charAt(j + i)) temp--;
dp[j][j + i] = Math.min(dp[j][j + i], temp);
}
}
}
return dp[0][n - 1];
}
The problem wants us to find the number of ways to do something without giving specific steps like how to achieve it. This can be a typical signal that dynamic programming may come to help.
dp[i][j] stands for the minimal turns we need for string from index i to index j.So we have
dp[i][i] = 1: we need 1 turn to paint a single character.dp[i][i + 1]dp[i][i + 1] = 1ifs.chartAt(i) == s.charAt(i + 1)dp[i][i + 1] = 2ifs.chartAt(i) != s.charAt(i + 1)
Then we can iteration
len from 2 to possibly n. For each iteration, we iteration start index from 0 to the farthest possible.- The maximum turns for
dp[start][start + len]islen + 1, i.e. print one character each time. - We can further divide the substring to two parts: start -> start+k and start+k+1 -> start+len. It is something as following:
index |start ... start + k| |start + k + 1 ... start + len| char | a ... b | | c ... b |- As shown above, if we have
s.charAt(start + k) == s.charAt(start + len), we can make it in one turn when we print this character (i.e.bhere) - This case we can reduce our turns to
dp[start][start + k] + dp[start + k + 1][start + len] - 1
- As shown above, if we have
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 i = 0; i < n; i++) {
dp[i][i] = 1;
if (i < n - 1) {
dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 1 : 2;
}
}
for (int len = 2; len < n; len++) {
for (int start = 0; start + len < n; start++) {
dp[start][start + len] = len + 1;
for (int k = 0; k < len; k++) {
int temp = dp[start][start + k] + dp[start + k + 1][start + len];
dp[start][start + len] = Math.min(
dp[start][start + len],
s.charAt(start + k) == s.charAt(start + len) ? temp - 1 : temp
);
}
}
}
return dp[0][n - 1];
}
Time complexity is
O(n^3)
Some simple optimization. Consecutive repeating characters do not affect our printing as we can always print them together. i.e
aaabbb is equivalent with ab. So we can reduce the string first which somehow reduce nStringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
continue;
}
sb.append(s.charAt(i));
}
s = sb.toString();
This helps reduce running time from 60ms to 53ms.
We start with a string of len n. This string can be decomposed to two substrings of len n-1 and len 1. There are only two possible start indexes of the substring with len n-1. If the initial character of two substrings are same, then we can have one less turn. Each substring can be decomposed further until reaching the boundary case, a substring with len 1.
So basically, this DP solution caches all possible decomposition cases from substring of len 1 starting from any possible index. Then we build the string from the scratch until we are able to build the whole input string.
public int strangePrinter(String s) {
if(s.isEmpty()) return 0;
int[][] dp = new int[100][100];
//boundary case, substring with len 1, i.e. char at each index
for(int i = 0; i < 100; i++){
dp[i][i] = 1;
}
for(int len = 2; len <= s.length(); len++){
for(int start = 0; start + len <= s.length(); start++){
dp[start][start+len-1] = len;
for(int split = start + 1; split <= start + len -1; split++){
int result = dp[start][split-1] + dp[split][start + len -1];
if(s.charAt(start) == s.charAt(split)){
result --;
}
dp[start][start+len-1] = Math.min(result, dp[start][start+len-1]);
}
}
}
return dp[0][s.length()-1];
}https://leetcode.com/problems/strange-printer/discuss/152758/Clear-Logical-Thinking-with-Code
X. Proof
We will first prove this inefficient algorithm to be correct, and then tune it so that it runs in O(n^3) time.
#python code
def strangePrinter(self, S):
def solve(l, r):
if l > r: return 0
ans = solve(l+1, r) + 1
for k in range(l+1, r+1): #[l+1,r]
if S[k] == S[l]:
ans = min(ans, solve(l, k-1) + solve(k+1, r))
return ans
return solve(0, len(S) - 1)
In the proof, lets imagine that solve(l, r) not only finds the minimum necessary number of prints, but also finds an optimal print sequence that achieves this number of prints.
PROOF START:
solve(l,r) finds an optimal print sequence to print s[l,r] over range [l,r] from scratch. What should be the first print in this sequence?
Given that we need to paste over all cells in [l,r], one option for a first print that is always optimal is to print s[l] over the entire range.
So, lets just agree to always do this as the first print.
proof by substitution:
Take an arbitrary sequence of prints which optimally prints s[l,r] over [l,r] from scratch.
There is exactly one print over cell l which prints s[l]. Lets say that it prints over the range [l,x], and that it was the ith print.
Now, we create new sequence of prints, as follows
1: print s[l] over the entire range [l,r]
2: do all prints before the ith print, BUT ignore any part of the prints over the range [l,x]. If an entire print lies within [l,x], skip it.
3: do all prints after the ith print.
This new sequence prints exactly the same thing as the old sequence of prints. However, it does it in fewer or equal number of prints.So, lets just agree to always do this as the first print.
Now, we know that the optimal print sequence that solve(l,r) will find starts w/ one print of s[l] over [l,r]. Afterwards, it does some optimal subsequent prints to finish off the range.
In the (not yet known) optimal print sequence that solve(l,r) ends up finding, there will be some cells in [l,r] which do not get pasted over again after that first print. Lets denote the rightmost of these cells as the pivot.
There are two possible cases for the pivot:
- The pivot is cell l.
After doing the first print s[l] over [l,r], all the cells in [l+1,r] need to be pasted over again, so we need to print s[l+1,r] over [l+1,r] from scratch. The optimal print sequence of solve(l+1,r) does exactly this.
- The pivot is not cell l.
Lets denote the pivot as k, where l<k<=r and s[k] == s[l].
The algorithm logic asserts that if k is an optimal pivot, an optimal print sequence for solve(l,r) has the same number of prints as solve(l,k-1) and solve(k+1,r) combined. Why is this true?
Lets think about the optimal print sequence that solve(l,k-1) finds. It first prints s[l] over [l,k-1] and then does optimal subsequent prints to finish off the range [l,k-1].
Notice that after solve(l,r) first prints s[l] over [l,r], it can copy the "optimal subsequent prints" of solve(l,k-1) to finish off the subrange [l,k-1].
This is because the conditions under which they must finish off range [l,k-1] are IDENTICAL. Namely,
i. All cells in the range have value s[l], initially.
ii. Any print on this range cannot extend left of l nor right of k-1.
i. All cells in the range have value s[l], initially.
ii. Any print on this range cannot extend left of l nor right of k-1.
For solve(l,r), a print on the range [l,k-1] cannot extend right of k-1, because k is the pivot (note the definition of pivot).
Lastly, solve(l,r) must print s[k+1,r] over subrange [k+1,r] from scratch. We can copy the optimal print sequence of solve(k+1,r) to do this.
These observations lead to a straightforward way of constructing an optimal print sequence for solve(l,r) under the assumption that the optimal pivot is k.
i. First print s[l] over [l,r]
ii. Copy the optimal subsequent prints found by solve(l,k-1) to finish off range [l,k-1]
iii. Copy the optimal print sequence found by solve(k+1,r) to do range [k+1,r]
i. First print s[l] over [l,r]
ii. Copy the optimal subsequent prints found by solve(l,k-1) to finish off range [l,k-1]
iii. Copy the optimal print sequence found by solve(k+1,r) to do range [k+1,r]
Notice that this print sequence has exactly the same number of prints as solve(l,k-1) and solve(k+1,r) combined.
Lastly, we don't know what the optimal pivot is initially, but since solve(l,r) tries out all candidates, it is guarenteed to find the optimal print sequence overall.
This concludes the proof that the algorithm is correct.
Now, to speed up computation, we will augment our algorithm w/ memoization.
def strangePrinter(self, S):
memo = {}
def solve(l, r):
if l > r: return 0
if (l, r) not in memo:
ans = solve(l+1, r) + 1
for k in range(l+1, r+1): #[l+1,r]
if S[k] == S[l]:
ans = min(ans, solve(l, k-1) + solve(k+1, r))
memo[l, r] = ans
return memo[l, r]
return solve(0, len(S) - 1)
Comparing the original algorithm to this augmented version, one can see that the memoization does not affect what is returned by any subproblem. Therefore, the algorithm is still correct.
However, the time complexity has been reduced from exponential time to O(n^3).
However, the time complexity has been reduced from exponential time to O(n^3).
https://leetcode.com/problems/strange-printer/discuss/112489/C%2B%2B-solution-and-proof-with-optimal-substructure
https://blog.vrqq.org/archives/31/
https://blog.vrqq.org/archives/31/
先将原字符串去重，得到新的字符串ss。
设dpi为字符串ss[i...j]所需要的最小次数，有如下条件：
设dpi为字符串ss[i...j]所需要的最小次数，有如下条件：
dfs(int left, int right) {
...calculate...
return dp[left][right];
}
初始条件: dp[i][i]=1;
所求答案dfs(0,ss.size()-1);
for each k in left<k<=right:
if (ss[left]==ss[k])
dp[left][right]=min(dp[left+1][k-1]+dp[k][right]);
先看初始条件:
比如一个字符串abaca，对于第一个字符，无论能不能跟后面凑上一波，他都要打印。于是，我们需要遍历如下几种可能：
1、他自己独占一次打印区间。（结果为a _ _）
2、他自己和第三个字母在一波打印。（结果为aaa _ _）
3、他自己和第三个第五个字母一波打印出来。结果为（aaaaa）
对于每次打印，如果打印区间末尾会被其他覆盖掉，那么末尾就没意义，比如第一次打印完是：aaaa_，第二次打印完是aaacc，覆盖掉了上一次的末尾，那么末尾打这么长就没意义，干脆就打三个aaa就可以了。
因此我们规定：对于每次for循环中求dp的结果dpl，[l+1...k-1]区间内颜色无意义（先假定正确，最后有解释），l位和k位一经涂刷，便不会被后面的涂刷覆盖掉，但[l+1...k-1]这个部分可以随便覆盖。
关于这个规定的解释：
l位就是最边上的位置，无论“自己独占一次打印”和“跟别人凑一波”，怎么着都得打，所以规定此次打印颜色位l位的颜色。
r位也是最靠边一位，如果说最优解是“r位被覆盖掉了”，那么这个区间延伸到r就没意义，干脆缩短点就行，理由如上。
比如一个字符串abaca，对于第一个字符，无论能不能跟后面凑上一波，他都要打印。于是，我们需要遍历如下几种可能：
1、他自己独占一次打印区间。（结果为a _ _）
2、他自己和第三个字母在一波打印。（结果为aaa _ _）
3、他自己和第三个第五个字母一波打印出来。结果为（aaaaa）
对于每次打印，如果打印区间末尾会被其他覆盖掉，那么末尾就没意义，比如第一次打印完是：aaaa_，第二次打印完是aaacc，覆盖掉了上一次的末尾，那么末尾打这么长就没意义，干脆就打三个aaa就可以了。
因此我们规定：对于每次for循环中求dp的结果dpl，[l+1...k-1]区间内颜色无意义（先假定正确，最后有解释），l位和k位一经涂刷，便不会被后面的涂刷覆盖掉，但[l+1...k-1]这个部分可以随便覆盖。
关于这个规定的解释：
l位就是最边上的位置，无论“自己独占一次打印”和“跟别人凑一波”，怎么着都得打，所以规定此次打印颜色位l位的颜色。
r位也是最靠边一位，如果说最优解是“r位被覆盖掉了”，那么这个区间延伸到r就没意义，干脆缩短点就行，理由如上。
给两个测试数据并且来说一个错误的dp方程：
ss1=abaca
ss2=acbabca
错误的dp方程：
for each i in l<k<=j:
if (ss[l]==ss[k])
dp[l][r] = min(dp[l][r], 1+dfs(l+1,k-1)+(k==r?0:dfs(k+1,r)));
正确的dp方程：dp[left][right]=min(dp[left][right], dp[left+1][k-1]+dp[k][right]);
这个错误dp方程使用ss1验证，得到答案4次，应该是3次。
对比正确的方程，我们发现正确的方程很好的处理了a_a_a这种情况.正确的dp方程对于abaca,先找到ss[0]==ss[2]，然后把此次涂刷颜色a的“1次”计算在了dp2这个里面，还保留了颜色信息“a”。
对比正确的方程，我们发现正确的方程很好的处理了a_a_a这种情况.正确的dp方程对于abaca,先找到ss[0]==ss[2]，然后把此次涂刷颜色a的“1次”计算在了dp2这个里面，还保留了颜色信息“a”。
看到这里再反过来介绍我们的规定中“对于每次求dp的结果dpl，[l+1...k-1]区间内颜色无意义”
因为每次for循环里面，[l+1]位肯定是需要涂刷的，并且l+1位颜色和前后都不一样（l位和l+2位，去重了），无论如何都要在[l+1...k-1]区间内涂一个ss[l+1]这个颜色，无论涂多长多短，并且以后的任意一次涂刷都不会跨越[l,k]区间。
因为每次for循环里面，[l+1]位肯定是需要涂刷的，并且l+1位颜色和前后都不一样（l位和l+2位，去重了），无论如何都要在[l+1...k-1]区间内涂一个ss[l+1]这个颜色，无论涂多长多短，并且以后的任意一次涂刷都不会跨越[l,k]区间。
好啦差不多就是这个意思了，如果不理解，先试着理解错误的方程，然后再找出其中的错误。
