博弈论 DP：Nim 游戏与石头游戏

预测赢家（LeetCode 486）

两人轮流从数组两端取数，先手是否一定赢（先手得分 >= 后手得分）：

dp[i][j] = 在 nums[i..j] 这个子数组中，先手比后手多得的最大分数：

public boolean predictTheWinner(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][n];
    // 只有一个元素时先手直接取
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            // 先手取左端：nums[i] - 后手在 [i+1,j] 的优势
            // 先手取右端：nums[j] - 后手在 [i,j-1] 的优势
            dp[i][j] = Math.max(nums[i] - dp[i+1][j],
                                nums[j] - dp[i][j-1]);
        }
    }
    return dp[0][n-1] >= 0; // 先手优势 >= 0 说明先手赢
}

石子游戏（LeetCode 877）

数组长度为偶数且总数为奇数，先手一定赢（数学结论）；用DP也可解：

// 数学：先手一定可以选所有奇数位或所有偶数位，选最大的那组
public boolean stoneGame(int[] piles) {
    return true; // 先手必赢
}

// DP 同预测赢家，通用解法
public boolean stoneGameDP(int[] piles) {
    int n = piles.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = piles[i];
    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
        }
    return dp[0][n-1] > 0;
}

石子游戏 VII（LeetCode 1690）

取端点石子不得分，得分是剩余石子之和；求先手比后手最大得分差：

dp[i][j] = nums[i..j] 中先手比后手最大差值：

public int stoneGameVII(int[] stones) {
    int n = stones.length;
    int[] prefix = new int[n+1];
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + stones[i];
    int[][] dp = new int[n][n];
    // 子数组和 = prefix[j+1] - prefix[i]
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            int sumExLeft  = prefix[j+1] - prefix[i+1];  // 取走左端后剩余
            int sumExRight = prefix[j]   - prefix[i];    // 取走右端后剩余
            dp[i][j] = Math.max(sumExLeft - dp[i+1][j], sumExRight - dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

总结