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 initially they are arranged so that no adjacent cards are of the same type. The game goes as follows:

1. The player chooses a card and removes it. This means the cards on the left and the right are now adjacent.
2. While the (now adjacent) left and right cards are of the same type, remove both cards and add one to the score.
3. 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 since n <= 1000, it definitely gets TLE verdict:

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?