STONE GAME MEDIUM
problema
Há um número par de pilhas de pedras em fila, e a pilha i tem piles[i] pedras.
O total de pedras é ímpar, então não existe empate. Alice começa e os dois se alternam. Na sua vez, o jogador
pega uma pilha inteira de uma das pontas da fila. Quem tiver mais pedras no fim vence.
Os dois jogam de forma ótima. Retorne true se Alice vencer.
piles = [3, 9, 1, 2] → true
Alice pega 2. Bob fica entre 3 e 1: se pegar 3, Alice pega 9; se pegar 1, Alice pega 9 também. Alice termina com 11 ou mais.
piles = [5, 3, 4, 5] → true
Pegando a primeira pilha (5), Alice garante 9 pedras contra 8: apertado, mas vence.
Restrições: 2 ≤ piles.length ≤ 500, com tamanho par · 1 ≤ piles[i] ≤ 500 · soma de piles é ímpar
Pinte as pilhas alternadamente: posições pares e ímpares. Como a quantidade é par, Alice sempre pode pegar
todas as pilhas de uma mesma cor: se ela pega uma ponta par, as duas pontas que sobram para Bob são ímpares, e vice-versa.
Uma das cores soma mais (a soma total é ímpar), então Alice escolhe essa cor e vence. A resposta é sempre
true, em O(1). A DP abaixo é a solução geral, que também diz por quanto ela vence, e é a mesma do
Predict the Winner.