力扣486预测赢家 极小化极大 动态规划

question

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int dp[][] = new int[n][n]; //dp[i][j]是在i-j内当前玩家先手取数能领先对手的最大值

        for (int i = 0; i < n; ++i) {
            dp[i][i] = nums[i];
        }

        for (int j = 1; j < n; ++j) {
            for (int i = j - 1; i >= 0; --i) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            //取左端点和取右端点
            }
        }

        return dp[0][n - 1] >= 0;
    }
}