关注Java领域相关技术 记录有趣的事情

LeetCode-486. 预测赢家

US-B.Ralph
US-B.Ralph
2020-09-01

问题地址

LeetCode每日一题/2020-09-01

LeetCode486. 预测赢家

问题描述

规则

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例1

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。

示例2

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。

最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

提示

  • $1 \leq 给定的数组长度 \leq 20$。
  • 数组里所有分数都为非负数且不会大于 10000000 。
  • 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

解析

解题思路

  • 我们可以想到使用递归，以[1, 5, 233, 7]为例：
    • 如果玩家1选择的是1，那么玩家2只能在[5, 233, 7]中选择；
    • 如果玩家1选择的是7，那么玩家2只能在[1, 5, 233]中选择；
  • 由以上分析，设数组两端索引为l、r那么：
    • 如果玩家1选择nums[l]，那么玩家2只能从[l+1,…,r]中选择数字；
    • 如果玩家1选择nums[r]，那么玩家2只能从[l,…,r-1]中选择数字；

复杂度分析

  1. 时间复杂度，O(2^n)，其中 n 是数组的长度。
  2. 空间复杂度，O(n)。其中 n 是数组的长度。空间复杂度取决于递归使用的栈空间。

数据操作分析

  • 分别计算玩家1选择l端和选择r端后与玩家2所得分数的差值。
  • 返回choiceL、choiceR中较大的数值choiceMax。
  • 如果choiceMax >= 0，则返回true。

编码实现

public class LeetCode0486_PredictTheWinner {
    public boolean PredictTheWinner(int[] nums) {
        return choice(nums, 0, nums.length - 1) >= 0;
    }
    //l和r分别是nums两端的索引
    private int choice(int[] nums, int l, int r) {
        if (l == r) return nums[l];//递归退出条件
        int choiceL = nums[l] - choice(nums, l + 1, r);//选择左端的结果
        int choiceR = nums[r] - choice(nums, l, r - 1);//选择右端的结果
        return Math.max(choiceL, choiceR);
    }
}

官方解法

递归

思路：
  • 为了判断哪个玩家可以获胜，需要计算一个总分，为先手得分与后手得分之差。当数组中的所有数字都被拿取时，如果总分大于或等于 0，则先手获胜，反之则后手获胜。
  • 由于每次只能从数组的任意一端拿取数字，因此可以保证数组中剩下的部分一定是连续的。
  • 假设数组当前剩下的部分为下标 \textit{start} 到下标 \textit{end} ，其中 0 \le \textit{start} \le \textit{end}<\textit{nums}.\text{length}。
  • 如果\textit{start}=\textit{end}，则只剩一个数字，当前玩家只能拿取这个数字。
  • 如果\textit{start} j 时，dp[i][j]=0。
  • 当 i=j 时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 0 <= i，都有 dp[i][j]=nums[i]。
  • 当i<j时，当前玩家可以选择nums[i]或nums[j]，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：

dp[i][j]=max(nums[i] – dp[i + 1][j], nums[j] – dp[i][j – 1])

  • 最后判断 dp[0][nums.length-1] 的值，如果大于或等于 0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。

复杂度分析：
  1. 时间复杂度，O(n^2)，其中 n 是数组的长度。需要计算每个子数组对应的 \textit{dp} 的值，共有 \frac{n(n+1)}{2} 个子数组。
  2. 空间复杂度，O(n)。其中 n 是数组的长度。空间复杂度取决于额外创建的数组\textit{dp}，如果不优化空间，则空间复杂度是 O(n^2)，使用一维数组优化之后空间复杂度可以降至 O(n)。
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }
}
  • 上述代码中使用了二维数组 \textit{dp}。分析状态转移方程可以看到:
    • $\textit{dp}[i][j]$ 的值只和 $\textit{dp}[i + 1][j]$ 与 $\textit{dp}[i][j – 1]$ 有关，即在计算 $\textit{dp}$ 的第 $i$ 行的值时，只需要使用到 $\textit{dp}$ 的第 $i$ 行和第 $i+1$ 行的值，因此可以使用一维数组代替二维数组，对空间进行优化。
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[length - 1] >= 0;
    }
}

拓展练习

  • 读者在做完这道题之后，可以做另一道类似的题：「877. 石子游戏」。和这道题相比，第 877 题增加了两个限制条件：
    • 数组的长度是偶数；
    • 数组的元素之和是奇数，所以没有平局。
  • 对于第 877 题，除了使用这道题的解法以外，能否利用上述两个限制条件进行求解？

精彩评论

跳转地址：「手画图解」三种写法：递归、记忆化递归、动态规划

递归 思路

  • 以 [1, 5, 233, 7] 为例，玩家 1 先手。
    • 如果玩家 1 先选左端 1，则玩家 2 在 [5, 233, 7] 的两端中选。
    • 如果玩家 1 先选右端 7，则玩家 2 在 [1, 5, 233] 的两端中选。
    • 容易想到递归，怎么去定义递归的问题呢？ 我们先画图看看：
  • 可以看到，每个节点都是其中一个玩家在选择。当前子问题下，谁的分数更多，谁就赢。
    • 当前，你选了 x，得 x 分，他没选，得 0 分，你赢了别人 x 分，接下来呢？他选，然后你选……你们交替地得分……打住，你已进入递归的细节，别想下去了。
    • 当前，你有x分，对手有0分，在后面的游戏中，对手超过你y分。如果有x减y大于等于0，那你赢咯。
  • 别操心递归的细节，细节丢给子调用去做，眼睛盯着当前的 x 分，想想子调用应该返回什么，去和当前的 x 分作比较，判断出胜利。

  • 于是，递归函数做的事：计算当前做选择的玩家能赢过对手的分数。如果大于零，则表示他在这个子问题中赢了。
  • 怎么计算呢？当前选择的分数，减去，接下来对手赢过自己的分数（剩余数组的递归结果），因为选择有两种，所以我们二者取其大。
const PredictTheWinner = (nums) => {
  const helper = (i, j) => { // i，j是两端的索引
    if (i == j) { // 递归的出口，此时只有一个选择，并且没有剩余的可选
      return nums[i];
    }
    const pickI = nums[i] - helper(i + 1, j); // 选择左端
    const pickJ = nums[j] - helper(i, j - 1); // 选择右端
    return Math.max(pickI, pickJ);            // 取较大者
  };
  return helper(0, nums.length - 1) >= 0;
};

记忆化递归

  • 我们做了哪些重复的计算呢？
    • 比如，你先选 1，我再选 7，和你先选 7，我再选 1，这两种所带来的子问题是一样的，都是剩下[5, 233]。我们用数组或哈希表去存储计算过的子问题的解，下次遇到重复的子问题，就不用再次递归计算。
const PredictTheWinner = (nums) => {
  const len = nums.length;

  const memo = new Array(len);
  for (let i = 0; i < memo.length; i++) {
    memo[i] = new Array(len);
  }

  const helper = (i, j) => {
    if (memo[i][j] !== undefined) {
      return memo[i][j]; 
    }
    if (i == j) {
      memo[i][j] = nums[i];
      return nums[i];
    }
    const pickI = nums[i] - helper(i + 1, j);
    const pickJ = nums[j] - helper(i, j - 1);
    memo[i][j] = Math.max(pickI, pickJ);
    return memo[i][j];
  };

  return helper(0, len - 1) >= 0;
};

动态规划

  • 在递归中，我们看到大问题的拆解，看到子问题如何一个个被计算出来，我们现在用简单的循环取代递归，按顺序求解子问题，去填这个二维数组，而不是依靠递归去帮我们做这件事。
  • 动态规划是不带重复计算的递归，是一种聪明的递归。它把中间子问题的解存储在一维或多维数组中，我们不应该把思考的重心放在怎么填表，而是应该先想出正确的递归。
  • 只要我们记忆化了正确的递归，就容易看出适不适合用动态规划，DP 代码也就水到渠成。如果递归思考出错，就会写不出正确的 DP。
DP 求解
  • 有了对递归的思考，在记忆化递归的基础上，代码稍作修改即可。
  • 比照递归函数的定义，我们有 dp[i][j] 的定义：当前玩家在数组 [i:j] 中先手，赢过对方的分数。
  • 比照递归的结束条件，我们有 base case：当 i == j 时，dp[i][j] = nums[i];
  • 比照递归函数的返回值：

$$
Math.max(nums[i] – helper(i + 1, j), nums[j] – helper(i, j – 1))
$$

  • 我们有状态转移方程：

dp[i][j] = Math.max(nums[i] – dp[i + 1][j], nums[j] – dp[i][j – 1]);

  • 注意，要满足i <= j，所以只用填半张表。
  • 我们看看状态转移的方向，它会告诉我们填表时应该采用的计算方向，才不会出现：求当前的状态，它依赖的状态却还没求出来。

const PredictTheWinner = (nums) => {
  const len = nums.length;

  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len);
  }
  // base case
  for (let i = 0; i < len; i++) { 
    dp[i][i] = nums[i];
  }
  // iteration
  for (let i = len - 2; i >= 0; i--) { 
    for (let j = i + 1; j < len; j++) {
      const pickI = nums[i] - dp[i + 1][j];
      const pickJ = nums[j] - dp[i][j - 1];
      dp[i][j] = Math.max(pickI, pickJ);
    }
  }

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

复盘总结

  • 这三板斧的思路和代码是一气呵成的，彼此有着高度的联系。
  • 动态规划解法最难的部分是：准确描述出，或者说，定义出子问题。
  • 我们可以从递归出发，画画递归树，想想递归函数怎么定义？递归公式是什么？
  • 我们证明了子问题的最优解可以从规模较小的子问题的最优解中获得，就有了递推公式。
  • 接着，要确定出求解子问题的顺序，作为辅助，我们可以画出一个子问题依赖关系的关系图，一个节点就是一个子问题，边代表依赖关系。
  • 看看这个图是否是一个有向无环图，如果存在环形依赖，则用不了动态规划。
  • 然后我们基于该图，采用合适的计算顺序，自底（base case）而上地计算。
  • 如果我们只想求出最优解的值，则任务完成。如果要找出所有的最优解，那么 DP 是无能为力的，必须要用回溯去构建出我们的答案。
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

15 − 8 =