Codeforces

Start Small, Stay Small

One of my favourite DP problems is 1132F: Clear the String.

Hints on CF Step.

Define dp[i][j] as the minimum number of operations to clear the string str[i ... j]. The first thought that comes to mind for transitions is to clear a substring of equal characters str[x ... y] and then combine the answers from the left and right half, i.e dp[i][x - 1] and dp[y + 1][j]. However, you can’t combine them since those parts aren’t independent anymore.

A clever trick to make sure that the parts become independent is to start small. Instead of clearing the first substring of equal characters, focus on the first character, str[i]. It can either be cleared alone, or it can be merged with some identical character str[k]. But merging can only happen if you can clear str[i + 1 .... k - 1] independently. And after the merge, str[k .... j] can be cleared independently.

Just by changing our perspective, we were able to perform transitions so easily.