Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Optimizing n^3 DP

Revision en5, by szawinis, 2017-03-22 18:52:39

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]+(a[i] == a[j]))

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)