486. 预测赢家 java

题目：力扣

解题思路：

1、递归

2、记忆化递归

3、动态规划（滑动数组）

参考：力扣

递归代码 (关键是choose_l，choose_r的理解）

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return helper(nums, 0 , nums.length-1) >= 0;
    }
    public int helper(int[] nums, int left, int right){
        if(left == right){
            return nums[left];
        }
        int choose_l = nums[left] - helper(nums, left+1, right);
        int choose_r = nums[right] - helper(nums, left, right-1);
        return Math.max(choose_l, choose_r);
    }
}

 

记忆化递归

class Solution {
    int[][] dp;
    public boolean PredictTheWinner(int[] nums) {
        int len = nums.length;
        dp = new int[len][len];
        return helper(nums, 0 , len-1) >= 0;
    }
    public int helper(int[] nums, int left, int right){
        if(dp[left][right] > 0){
            return dp[left][right];
        }
        if(left == right){
            dp[left][right] = nums[left];
            return nums[left];
        }
        int choose_l = nums[left] - helper(nums, left+1, right);
        int choose_r = nums[right] - helper(nums, left, right-1);
        dp[left][right] = Math.max(choose_l, choose_r);
        return dp[left][right];
    }
}

 

动态规划

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][len];
        for(int i = 0; i < len; i++){
            dp[i][i] = nums[i];
        }
        for(int i = len-2; i >= 0; i--){
            for(int j = i+1; j < len; j++){
                dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }
        return dp[0][len-1] >= 0;
    }
}

 使用滑动数组

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            dp[i] = nums[i];
        }
        for(int i = len-2; i >= 0; i--){
            for(int j = i+1; j < len; j++){
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j-1]);
            }
        }
        return dp[len-1] >= 0;
    }
}