[LeetCode] 1531. String Compression II

Link here

I thought it should be Greedy at first, but was stuck in Example 2. Then, I considered about DP, but found it hard to figure out how to build the larger solution from the sub-problem.

So, another time I reached out for solution.

We use dp[i][j] to represent the minimum length of the first i letters after compression and after j deletions.

It obvious that if we delete the i-th letter, and then dp[i][j] = dp[i-1][j-1].

If we don’t, we can scan the former string sequence to try to “combine” the letters.