Hints: Clear the String

Define dp[i][j] to be the minimum number of operations required to reduce string str[i ... j] to an empty string. Is it possible to populate this DP table efficiently?

Here’s a possible DP transition: When you are asked to compute the answer for [i ... j], you know that the first deletion would be a substring of equal characters inside [i ... j]. Hence, we can try out all consecutive maximal substrings as the first cut, and then query the DP table for the subproblem of the left and right half.

Can you figure out what’s wrong with this appraoch?

The above approach won’t work because the left and right halves are not independent.

For example, if the string is aba, then making the first cut at b would give you the answer for the entire string as 1 + 1 + 1, when in fact, we can combine left and right half after the cut.

Hence, we need to be smart about our DP transitions. We should make the initial choice in such a way that the resulting subproblems are disjoint and can be solved independently.

Instead of focusing your first cut on a big substring (which will create a gap in the middle), try thinking small, and focus on the ends instead of the middle.

Consider the first character of the substring str[i ... j]. What choices does it have?

When the time comes, it is deleted alone.

What is the total cost incurred for this choice?

1 + dp[i + 1][j]

When the time comes, it is merged with some identical element from the substring.

However, there can be multiple identical characters in the substring. How do we know which one is the optimal to merge with?

What is the total cost incurred for this choice?

Since we do not know the optimal position, let’s try all positions. Assume that it needs to be merged with the character at position k. To get there, substring [i + 1 ... k - 1] should be collapsed without any interaction from outside elements. Also, once the merge happens, we can just forget that the first character ever existed, and ask ourselves, what is the minimum cost to reduce [k .... j] to an empty string.

Notice how a smart transition choice made these 2 problems independent by creating a wall between them.

dp[i][j] = min(dp[i + 1][k - 1] + dp[k][j]) where str[i] == str[k] and k is inside the given range.