石子游戏 II

/*
 * 思路：使用动态规划来解决这个问题。dp[i][M]表示当剩下的石子堆为piles[i:]时，M的值为M时，当前玩家最多可以拿到的石子数量。
 * 我们从后向前计算，最终dp[0][1]就是我们要的答案。
 */
import java.util.stream.IntStream;

public class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n + 1];
        int[] suffixSum = new int[n];
        suffixSum[n - 1] = piles[n - 1];
        IntStream.range(0, n - 1).forEach(i -> suffixSum[n - 2 - i] = suffixSum[n - 1 - i] + piles[n - 2 - i]);
        IntStream.range(0, n).forEach(i -> {
            IntStream.range(1, n + 1).forEach(M -> {
                if (i + 2 * M >= n) {
                    dp[n - 1 - i][M] = suffixSum[n - 1 - i];
                } else {
                    IntStream.range(1, 2 * M + 1).forEach(X -> {
                        dp[n - 1 - i][M] = Math.max(dp[n - 1 - i][M], suffixSum[n - 1 - i] - dp[n - 1 - i + X][Math.max(M, X)]);
                    });
                }
            });
        });
        return dp[0][1];
    }
}