Medium

题目描述

给定一个整数数组 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 <= nums.length <= 20
  • 0 <= nums[i] <= 10^7

解题思路

这是一道经典的博弈论动态规划问题。我们需要考虑在最优策略下，玩家1是否能够获胜。

核心思路： 定义 dp[i][j] 表示在区间 [i, j] 内，当前玩家相对于另一个玩家的最大得分差。如果当前玩家选择左端点 nums[i]，那么在剩余区间 [i+1, j] 中，对手会获得最大优势 dp[i+1][j]，所以当前玩家的相对得分为 nums[i] - dp[i+1][j]。同理，选择右端点的相对得分为 nums[j] - dp[i][j-1]。

状态转移方程：

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

边界条件： 当 i == j 时，只有一个数字，当前玩家直接取走，得分差为 nums[i]。

最终判断 dp[0][n-1] >= 0 即可，如果玩家1的相对得分非负，说明玩家1能够获胜或平局。

时间复杂度分析：

  • 状态数量：O(n²)
  • 每个状态计算：O(1)
  • 总时间复杂度：O(n²)

这种解法也可以用记忆化递归实现，但动态规划的迭代实现更加直观和高效。

代码实现

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        
        // 填充dp表
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }
        
        return dp[0][n-1] >= 0;
    }
};

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        
        # 初始化对角线
        for i in range(n):
            dp[i][i] = nums[i]
        
        # 填充dp表
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        
        return dp[0][n-1] >= 0

public class Solution {
    public bool PredictTheWinner(int[] nums) {
        int n = nums.Length;
        int[,] dp = new int[n, n];
        
        // 初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i, i] = nums[i];
        }
        
        // 填充dp表
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = Math.Max(nums[i] - dp[i+1, j], nums[j] - dp[i, j-1]);
            }
        }
        
        return dp[0, n-1] >= 0;
    }
}

var predictTheWinner = function(nums) {
    const n = nums.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));
    
    // 初始化对角线
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }
    
    // 填充dp表
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
        }
    }
    
    return dp[0][n-1] >= 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要填充 n×n 的 dp 表，每个位置计算为 O(1)
空间复杂度O(n²)使用了 n×n 的二维数组存储状态

相关题目