Ming
0%

LeetCode-486

Posted on Edited on In

题目

结果

递归

DP

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return predictTheWinner(nums, 0, nums.length - 1, 1) >= 0;
    }

    private int predictTheWinner(int[] nums, int start, int end, int flag) {
        if (start == end) {
            return nums[start] * flag;
        }
        int left = predictTheWinner(nums, start + 1, end, -flag) + nums[start] * flag;
        int right = predictTheWinner(nums, start, end - 1, -flag) + nums[end] * flag;
        if (flag == 1) {
            return Math.max(left, right);
        } else {
            return Math.min(left, right);
        }
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = Math.max(-dp[i + 1][j] + nums[i], -dp[i][j - 1] + nums[j]);
            }
        }
        return dp[0][nums.length - 1] >= 0;
    }
}

复杂度

递归

时间复杂度：O（2^n）

空间复杂度：O（n），取决于递归的层数。

DP

时间复杂度：O（n²）

空间复杂度：O（n²）