LeetCode486-预测赢家

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/predict-the-winner/

中文链接：https://leetcode-cn.com/problems/predict-the-winner/

题目详述

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

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

示例 1:

1
2
3
4
5
6
输入: [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
2
3
4
输入: [1, 5, 233, 7]
输出: True
解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。
最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。

注意:

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

题目详解

  • 从最简单的情况考虑起，假设只有一个数，则玩家 1 只能选择这个数。
  • 考虑扩大问题的规模，玩家会存在两种决策：一种选择数组的头部，另一种选择数组的尾部。这两种情况下的子问题都可以提前算出。至此，可以知道应该使用动态规划。
  • 令 f(i, j) 表示闭区间 [i, j] 下玩家 1 能获得的最大分数。
  • 每次状态存在两种情况：
    • 当前是玩家 1 取数，f(i, j) = max(f(i + 1, j) + nums[i], f(i, j - 1) + nums[j])。表示从头部或尾部取数的最优情况。
    • 当前是玩家 2 取数，f(i, j) = min(f(i + 1, j), f(i, j - 1))。表示玩家 2 希望自己的分数尽可能大，这必然会导致玩家 1 的分数变小。
  • 初始状态，若最后一次是玩家 1 取数，则 f(i, i) = nums[i]；否则 f(i, i) = 0。
  • 状态由区间从短到长递推。
  • 最后玩家 1 得到的最大分数为 f(0, n - 1)，设总得分为 sum，按照题目要求，最终玩家 1 获胜的条件为 f(0, n - 1) >= sum - f(0, n - 1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LeetCode_00486 {

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] f = new int[n][n];
        boolean flag = (n & 1) == 1;
        if (flag) {
            for (int i = 0; i < n; ++i) {
                f[i][i] = nums[i];
            }
        }
        for (int len = 2; len <= n; ++len) {
            flag = !flag;
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                if (flag) {
                    f[i][j] = Math.max(f[i + 1][j] + nums[i], f[i][j - 1] + nums[j]);
                } else {
                    f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        int sum = Arrays.stream(nums).sum();
        return f[0][n - 1] >= sum - f[0][n - 1];
    }
}

通过分析易知，当数组长度为偶数时，玩家 1 必胜。可以在进行动态规划之前加一个判断进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class LeetCode_00486 {

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if ((n & 1) == 0) { // 长度为偶数必胜
            return true;
        }
        int[][] f = new int[n][n];
        boolean flag = (n & 1) == 1;
        if (flag) {
            for (int i = 0; i < n; ++i) {
                f[i][i] = nums[i];
            }
        }
        for (int len = 2; len <= n; ++len) {
            flag = !flag;
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                if (flag) {
                    f[i][j] = Math.max(f[i + 1][j] + nums[i], f[i][j - 1] + nums[j]);
                } else {
                    f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        int sum = Arrays.stream(nums).sum();
        return f[0][n - 1] >= sum - f[0][n - 1];
    }
}
  • 可以换一种思路进行动态规划。因为我们不关心最后的得分，只关心最后玩家 1 获得的分数是否大于等于玩家 2 获得的分数。
  • 令 dp(i, j) 为面对区间 [i, j] 的玩家比另一名玩家多获得的分数。
  • 则状态转移为：f(i, j) = max(nums[i] - f(i + 1, j), nums[j] - f(i, j - 1))。其中，玩家 A 选择位置 i 会立即获得分数 nums[i]，另一名玩家 B 面临的是区间 [i + 1, j]，代表在这个区间下他比玩家 A 多获得的分数，这个已经提前算出，因此 nums[i] - f(i + 1, j) 就代表选择位置 i 玩家比另一名玩家多获得的分数。选择位置 j 同理。两者最大值就是选择头部或尾部的最优情况。
  • 初始状态：f(i, i) = 0。区间由短到长递推。
  • 最终玩家 1 获胜的条件为 f(0, n - 1) >= 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00486 {

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if ((n & 1) == 0) {
            return true;
        }
        int[][] f = new int[n][n];
        for (int i = 0; i < n; ++i) {
            f[i][i] = nums[i];
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                f[i][j] = Math.max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
            }
        }
        return f[0][n - 1] >= 0;
    }
}

由于 f[i][j] 只与 f[i + 1][j] 和 f[i][j - 1] 有关，可以压缩空间，从二维降为一维，注意地推的方向做相应的变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00486 {

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if ((n & 1) == 0) {
            return true;
        }
        int[] f = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            f[i] = nums[i];
            for (int j = i + 1; j < n; ++j) {
                f[j] = Math.max(nums[i] - f[j], nums[j] - f[j - 1]);
            }
        }
        return f[n - 1] >= 0;
    }
}