877. Stone Game

Memo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean stoneGame(int[] piles) {
        Integer[][] memo = new Integer[piles.length][piles.length];
        return stoneGame(piles, 0, piles.length - 1, memo) > 0;
    }

    private int stoneGame(int[] piles, int i, int j, Integer[][] memo) {
        // 因为题目规定了石子堆数大于 0 且为偶数，所以此处无需处理 i > j 的情况
        if (i == j) {
            return piles[i];
        }

        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int chooseLeft = piles[i] - stoneGame(piles, i + 1, j, memo);
        int chooseRight = piles[j] - stoneGame(piles, i, j - 1, memo);
        memo[i][j] = Math.max(chooseLeft, chooseRight);
        return memo[i][j];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean stoneGame(int[] piles) {
        // 定义 dp[i][j] 为石子堆 piles[i]...[j] 时当前玩家的净得分，dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        int[][] dp = new int[piles.length][piles.length];

        // 当只有一堆石子时，另一个选手没有选择，此时净得分为最后一堆石子的分数
        for (int i = 0; i < piles.length; i++) {
            dp[i][i] = piles[i];
        }

        for (int i = piles.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < piles.length; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }

        return dp[0][piles.length - 1] > 0;
    }
}

References

877. Stone Game