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<br>↵
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?
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<br>↵
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?
