题目链接
预测赢家
题目描述
注意点
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 10^7
- 假设每个玩家的玩法都会使他的分数最大化
- 如果两个玩家得分相等，同样认为玩家1是游戏的赢家
解答思路
- 需要注意的是，如果数组中的元素个数为偶数，则玩家1始终都是游戏的赢家
- 首先可以使用递归找到各个区间能获得的最大分数，因为本题是要判断两个玩家都保证分数最大化的情况下玩家1的分数是否不比玩家2的分数低，所以递归时无论选择左侧数字还是右侧数字都应该减去下一次递归的最大值，最终dfs(nums, dp, 0, n - 1)返回的值就是都保证分数最大化时玩家1与玩家2的分数差。因为在递归的过程中各个区间的最大值可能有多次计算，所以可以使用dp数组保存区间内的最大分数，也就是记忆化递归
- 第二个方法则是动态规划，首先直到的是区间[i, i]对应的dp[i][i] = nums[i]，可以根据dp[i][j - 1]或dp[i + 1][j]对应的dp[i][j]的值，可从区间大小0推至n - 1对应的dp值，需要注意的是，推导dp的公式为dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])，无论选择左侧数字还是右侧数字仍然应该减去下一次递归的最大值（下一次轮到对手选择下一轮的最大值），最终根据dp[0][n - 1]的值是否不小于0判断玩家1是否是赢家
代码
方法一：
class Solution {public boolean predictTheWinner(int[] nums) {int n = nums.length;if (n % 2 == 0) {return true;}// dp[i][j]表示[i, j]区间内能获得的最大分数int[][] dp = new int[n][n];return dfs(nums, dp, 0, n - 1) >= 0;}public int dfs(int[] nums, int[][] dp, int left, int right) {if (left > right) {return 0;}if (dp[left][right] != 0) {return dp[left][right];}int leftVal = nums[left] - dfs(nums, dp, left + 1, right);int rightVal = nums[right] - dfs(nums, dp, left, right - 1);return Math.max(leftVal, rightVal);}
}
方法二：
class Solution {public boolean predictTheWinner(int[] nums) {int n = nums.length;if (n % 2 == 0) {return true;}// dp[i][j]表示[i, j]区间内能获得的最大分数int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {dp[i][i] = nums[i];}for (int len = 1; len < n; len++) {for (int i = 0; i + len < n; i++) {int j = i + len;dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);}}return dp[0][n - 1] >= 0;}
}
关键点
- 玩家1与玩家2的最终分数总和之差决定了谁是赢家
- 无论是记忆化递归还是动态规划dp所记录的始终是玩家1与玩家2的总分数之差
- 动态规划的思想
