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.
