Leetcode.486 预测赢家

题目链接

Leetcode.486 预测赢家 mid

题目描述

给你一个整数数组 nums 。玩家 $1$ 和玩家 $2$ 基于这个数组设计了一个游戏。

玩家 $1$ 和玩家 $2$ 轮流进行自己的回合，玩家 $1$ 先手。开始时，两个玩家的初始分值都是 $0$ 。每一回合，玩家从数组的任意一端取一个数字（即，$nums[0]$ 或 $nums[nums.length-1]$），取到的数字将会从数组中移除（数组长度减 $1$ ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 $1$ 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 $1$ 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：nums = [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：

输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

提示：

• $1\le nums.length\le 20$
• $0\le nums[i]\le 10^7$

解法：记忆化搜索

我们定义 $dfs(i,j)$ 为 当前先手 处于 $(i,j)$ 的局面，所能获得的最大的分。

• 当前先手 选择 $nums[i]$ 就会使得后手处于 $(i+1,j)$ 局面，即后手的最大得分为 $dfs(i+1,j)$；
• 当前先手 选择 $nums[j]$ 就会使得后手处于 $(i,j-1)$ 局面，即后手的最大得分为 $dfs(i,j-1)$；

先手要让后手得分尽可能的小，所以先手直接让后手选择较小的那个得分，即 m i n { d f s ( i + 1 , j ) , d f s ( i , j − 1 ) } min\{ dfs(i + 1,j),dfs(i ,j - 1)\} min{dfs(i+1,j),dfs(i,j−1)}。

因为无论怎么选择，先手后手得分总和是相同的。所以，后手的得分已经确定，那么此时先手的得分为 s u m ( i , j ) − m i n { d f s ( i + 1 , j ) , d f s ( i , j − 1 ) } sum(i,j) - min\{ dfs(i + 1,j),dfs(i ,j - 1)\} sum(i,j)−min{dfs(i+1,j),dfs(i,j−1)}。

当 $i=j$ 时，此时先手只能选择 $nums[i-1]$(下标从 $1$ 开始)。

最后我们只需要判断 $dfs(1,n)$ 是否大于总分 $sum(1,n)$ 的一半，即 $dfs(1,n)\times 2\ge sum(1,n)$。

时间复杂度：$O(n^2)$

C++代码：

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        for(int i = 1;i <= n;i++) s[i] = s[i - 1] + nums[i - 1];

        auto get = [&](int l,int r)->int{
            return s[r] - s[l - 1];
        };

        int f[n + 1][n + 1];
        memset(f,-1,sizeof f);

        function<int(int,int)> dfs = [&](int i,int j)->int{
            if(f[i][j] != -1) return f[i][j];
            if(i == j){
                f[i][j] = nums[i - 1];
                return f[i][j];
            }

            f[i][j] = get(i,j) - min(dfs(i + 1,j),dfs(i,j - 1));

            return f[i][j];
        };

        return dfs(1,n) * 2 >= get(1,n);
    }
};
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