Optimizing n^3 DP

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский 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 Английский szawinis 2017-03-22 18:15:44 10 Tiny change: 'otal, and they are ' -> 'otal, and initially they are ' (published)
en3 Английский szawinis 2017-03-22 18:15:03 92
en2 Английский 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 Английский szawinis 2017-03-22 18:13:36 922 Initial revision (saved to drafts)