题目给了个字符串，问打印几次能得到之。
想了半天 其实可以用记忆化搜索做 这个dp方程想做的简便 也是挺难想的
先将原字符串去重，得到新的字符串ss。
设dp[i][j]为字符串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的结果dp[l][k]，[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<=r:
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次”计算在了dp[2][4]这个里面，还保留了颜色信息“a”。
看到这里再反过来介绍我们的规定中“对于每次求dp的结果dp[l][k]，[l+1...k-1]区间内颜色无意义”
因为每次for循环里面，[l+1]位肯定是需要涂刷的，并且l+1位颜色和前后都不一样（l位和l+2位，去重了），无论如何都要在[l+1...k-1]区间内涂一个ss[l+1]这个颜色，无论涂多长多短，并且以后的任意一次涂刷都不会跨越[l,k]区间。
好啦差不多就是这个意思了，如果不理解，先试着理解错误的方程，然后再找出其中的错误。
本题终了，耗时3小时，果然菜是原罪。