传送门:https://leetcode-cn.com/problems/string-compression-ii/

题目大意:给你一个字符串，你可以删 k个 数。最后使得压缩字符串长度尽量小.

题目思路:dp

这个题目的核心点在于 观察最终方案是如何从原串中得到的 

有一点可以肯定：假设方案有k个部分，那么这k个部分一定是从原串的从左到右划分成k个区域，每个区域删除某些数得到连续的字符 而得来的。

假设一种方案为:  a3  b4  c5 ， 原串为 ....................

那么可以把原串看成三段: 

[这一段删除了若干个数，得到了三个连续的a][这一段删除了若干个数，得到了四个连续的b][这一段删除了若干个数，得到了五个连续的c]

这样以来，我们就可以用简单的子序列模型 dp 来转移。

对于每个字符ch，它要么在最终方案里，要么不在最终方案里。

ch不在: dp[i][j] = dp[i - 1][j - 1]

ch在方案中:根据的无后效性，我们可以简单的认为ch就是这一段的最右边。

现在我们需要从ch开始往前框住一段区间，枚举这个区间的左端点L:[L,i].然后将这一段删除非ch的数，留下全为ch的数。得到答案. dp[i][j] = min (dp[L-1][j - x] + y). // x是删除的个数,y是ch的压缩长度.

思路2：没验证,

思路来源于紫书上的方块消除。

对于区间最右端的字符，考虑有几种决策。

1.直接删掉

2.至此结算。

3.继续往前拼接.

这么转移即可。