Module dp

f(i, j) represents: when starting with piles[i..=j], the one who starts first will get f(i, j) more than the other one.

Note that 0 ≤ i ≤ j < piles.len() and f(i, j) might be negative.

If i == j, f(i, j) = piles[i]

Else,

f(i, j) = max(
    // the player takes piles[i]
    piles[i] - f(i + 1, j),
    // the player takes piles[j]
    piles[j] - f(i, j - 1),
)

The one who starts first will win the game if and only if f(0, n-1) > 0

Now the problem is to get f(0, n-1)

Functions

solve