Блог пользователя wildcraft

Dp problem
Автор wildcraft, 10 лет назад, По-английски

How do i solve this Dynamic Programming Problem link

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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].

→ Ответить