Optimizing n^3 DP

Revision en1, by szawinis, 2017-03-22 18:13:36

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:

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English szawinis 2017-03-22 18:52:39 15 Tiny change: 'i+1][j-1]+1)`\n\nIs t' -> 'i+1][j-1]+(a[i] == a[j]))`\n\nIs t'
en4 English szawinis 2017-03-22 18:15:44 10 Tiny change: 'otal, and they are ' -> 'otal, and initially they are ' (published)
en3 English szawinis 2017-03-22 18:15:03 92
en2 English szawinis 2017-03-22 18:13:55 4 Tiny change: 'ase:\n\n13\nN U B O ' -> 'ase:\n\n13<br>\nN U B O '
en1 English szawinis 2017-03-22 18:13:36 922 Initial revision (saved to drafts)