预测赢家
方法一：递归
以 [1, 5, 233, 7] 为例，玩家 1 先手。
如果他先选左端的 1，则玩家 2 在剩下的 [5, 233, 7] 的两端中选。
如果他先选右端的 7，则玩家 2 在剩下的 [1, 5, 233] 的两端中选。
容易想到递归。
加上当前已经得了$x$分，在后面的游戏中，对手总共赢了$y$分，如果$x >= y$，那么你就赢了。那么递归函数就需要计算出当前做选择的玩家赢过对手的分数，如果大于零，则代表他在这个子问题中赢了。
怎么计算呢？当前选择的分数，减去，往后对手赢过自己的分数（剩余数组的递归结果）。因为选择有两种，所以在两个差值中取较大的。
1 | class Solution { |
2 | public boolean PredictTheWinner(int[] nums) { |
3 | return helper(nums, 0, nums.length-1)>=0; |
4 | } |
5 | |
6 | public int helper(int[] nums, int i, int j){ |
7 | if(i == j){ |
8 | return nums[i]; |
9 | } |
10 | int a = nums[i] - helper(nums, i+1, j); |
11 | int b = nums[j] - helper(nums, i, j-1); |
12 | return Math.max(a, b); |
13 | } |
14 | } |
复杂度分析：
- 时间复杂度：$O(2^n)$
- 空间复杂度：$O(n)$
为了避免重复计算子问题，可以使用记忆化数组。
1 | class Solution { |
2 | int[][] memo; |
3 | public boolean PredictTheWinner(int[] nums) { |
4 | memo = new int[nums.length][nums.length]; |
5 | for(int i=0; i<nums.length; i++){ |
6 | Arrays.fill(memo[i], -1); |
7 | } |
8 | return helper(nums, 0, nums.length-1)>=0; |
9 | } |
10 | |
11 | public int helper(int[] nums, int i, int j){ |
12 | if(memo[i][j] != -1){ |
13 | return memo[i][j]; |
14 | } |
15 | if(i == j){ |
16 | memo[i][j] = nums[i]; |
17 | return nums[i]; |
18 | } |
19 | int a = nums[i] - helper(nums, i+1, j); |
20 | int b = nums[j] - helper(nums, i, j-1); |
21 | int ans = Math.max(a, b); |
22 | memo[i][j] = ans; |
23 | return ans; |
24 | } |
25 | } |
方法二：动态规划
在递归中，我们看到大问题的拆解，看到子问题如何一个个被计算出来，我们现在用简单的循环取代递归，按顺序求解子问题，去填这个二维数组，而不是依靠递归去帮我们做这件事。
动态规划是不带重复计算的递归，是一种聪明的递归。它把中间子问题的解存储在一维或多维数组中，我们不应该把思考的重心放在怎么填表，而是应该先想出正确的递归。
根据递归，那么定义dp[i][j]为当前玩家在[i:j]中先手，赢过对方的分数。
- $i==j$，那么 $dp[i][j]=nums[i]$。
- $i<j$，那么$dp[i][j]=max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])$。
1 | class Solution { |
2 | public boolean PredictTheWinner(int[] nums) { |
3 | int[][] dp = new int[nums.length][nums.length]; |
4 | int n = nums.length; |
5 | for(int i=0; i<n; i++){ |
6 | dp[i][i] = nums[i]; |
7 | } |
8 | for(int i=n-2; i>=0; i--){ |
9 | for(int j=i+1; j<n; j++){ |
10 | dp[i][j] = Math.max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]); |
11 | } |
12 | } |
13 | return dp[0][n-1]>=0; |
14 | } |
15 | } |
复杂度分析：
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$。