Problem Statement: There exists a single player game called "Pair of Fours". In this game, there are four types of cards, labeled 'U', 'B', 'O' and 'N'. There are N cards in total, and they are arranged so that no adjacent cards are of the same type. The game goes as follows:
- The player chooses a card and removes it. This means the cards on the left and the right are now adjacent.
- While the (now adjacent) left and right cards are of the same type, remove both cards and add one to the score.
- If there are no cards left, the game ends. Otherwise, go back to step one.
Sample case:
13 N U B O B U O N B O N U O
I came up with an O(n^3) DP solution, but fail to find a way to optimize it down to around O(n^2) with maybe a logarithmic factor:
dp[i][j] = max(dp[i][k]+dp[k+1][j], dp[i+1][j-1]+1)
Is there a way to optimize this, or is DP not the correct train of thought?