wildcraft's blog

Dp problem
By wildcraft, 10 years ago, In English

How do i solve this Dynamic Programming Problem link

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Let F[i] = best sum you can achieve when it's your turn and there are i elements left..

You can make a simple observation that if player A takes F[N] points then player B will have Total Points — F[n].

Based on that let Sum[i] be the sum of the last i elements in the stack then F[i] can be one of these 3 cases:

F[i] = A[i] + sum[i-1] -F[i-1].

F[i]= A[i] + A[i-1] + sum[i-2] -F[i-2].

F[i]= A[i] + A[i-1] + A[i-2] + sum[i-3] -F[i-3].

→ Reply