LeetCode 486 Predict the Winner(预测赢家)

2020-09-01 约 1678 字预计阅读 4 分钟

题目

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

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

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

示例 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 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

解题

设：总分 = 先手得分 - 后手得分。

当所有分数都被拿走后，如果总分>=0，就是先手胜，反之就是后手胜利。

由于是两个人分别拿，所以需要 turn 的正负来表示先手还是后手，在所有计算分数的地方都乘以 turn，使得总分就是差值。

最直观的思路就是用递归做出来，设数组两头的下标为 start 和 end。

递归函数中分别选择一个下标，计算选择下标之后递归计算出数组剩下的分被选择后的总分。

下标的分加上剩下的总分共有两种情况，取最大值，就是当前递归函数的总分。

递归中止条件为 start == end，这时候直接返回当前下标的值就好了。

递归解法

解：

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



class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        return total(nums, 0, nums.size() - 1, 1) >= 0;
    }

    int total(vector<int>& nums, int start, int end, int turn) {
        if (start == end) {
            return nums[start] * turn;
        }
        int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
        int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
        return max(scoreStart * turn, scoreEnd * turn) * turn;
    }
};

时间复杂度：O(2^n)，其中 n 是数组的长度。

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

动态规划解法

使用递归，存在大量重复计算，因此时间复杂度很高。可以试用动归解决这个问题。

用一个二维数组，记录计算过的总分。

dp[i][j] 为当前玩家在数组中，下标 i 到下标 j 的分数之差的最大值，当前玩家不一定是先手玩家。

根据题意，i不可能大于j。

当i==j时，dp[i][j] = nums[i];

计算分数的之差的最大值（状态转移）的公式是：

1

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

注意状态转移的方向，保证依赖的值已经有解。

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


class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int length = nums.size();
        auto dp = vector<vector<int>> (length, vector<int>(length));
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        // - 2是因为i == length - 1，这个值在刚刚已经算过了，只有一个值，即dp[i][i]
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }
};

经过观察，dp[i][j] 的值只和 dp[i+1][j] 与 dp[i][j−1] 有关。

即在计算第 i 行的值时，只使用到 dp 的第 i 行和第 i+1 行的值，而 j=i+1 ，所以大于 i+1 后面的行，都用不到了，可以借给 j 用。

列也只在意 j 和 j - 1 的值，所以就可以用一个数组来记录。

可以优化一下空间，把二维数组换成一维数组。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int length = nums.size();
        auto dp = vector<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] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[length - 1] >= 0;
    }
};

时间复杂度：O(n^2)，其中 n 是数组的长度。需要计算每个子数组对应的 dp 的值，共有 n(n+1)/2 个子数组。

空间复杂度：O(n)，其中 n 是数组的长度。空间复杂度取决于额外创建的数组 dp，如果不优化空间，则空间复杂度是 O(n^2)，使用一维数组优化之后空间复杂度可以降至 O(n)。

目录

LeetCode 486 Predict the Winner(预测赢家)

题目

解题

递归解法

动态规划解法