A ribbon holds a row of prize tokens with values tokens[0..n-1]; some are penalties, with negative
values. Two players take turns. On a turn a player cuts off between 1 and k tokens from one end
of the ribbon, either the left end or the right end, and keeps them. A player must take at least one
token when the ribbon is not empty, even if every choice hurts. The game ends when the ribbon is
empty.
Both players play perfectly, each maximising their own total minus the other's total. Return the first player's final total minus the second player's final total.
Examples
Input: tokens = [3, 9, 1, 2], k = 1
Output: 7
Explanation: taking 3 first lets the opponent take 9. Taking 2 first wins 9 later:
the first player ends with 2 + 9 = 11, the second with 3 + 1 = 4.
Input: tokens = [3, 9, 1, 2], k = 2
Output: 9
Explanation: take 3 and 9 (12). The opponent's best is to take 1 and 2 together (3).
Input: tokens = [-3, -3, -3], k = 2
Output: -3
Constraints
0 <= len(tokens) <= 300-100 <= tokens[i] <= 1001 <= k <= 4
Goals
- Describe a turn-based game by a small state (the remaining stretch of the ribbon)
- Use the negamax relation to turn a two-player game into one recurrence
- Fill the table bottom-up to avoid deep recursion