Predict the Winner,LeetCode,486

LeetCode 486题 “Predict the Winner” 是一个中等难度的动态规划问题。题目要求预测两个玩家在玩一个游戏时的胜者。游戏规则如下：

1. 给定一个整数数组 nums。
2. 两个玩家轮流从数组的两端选择一个数字，并将其从数组中移除。
3. 每个玩家总是尽可能使自己的得分最大化。
4. 玩家的得分是他们选择的数字的总和。
5. 预测玩家1（先手）是否能赢得游戏，或者两人是否会打成平手。

解题思路

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示在子数组 nums[i...j] 上，先手玩家能获得的最大分数与后手玩家能获得的最大分数之差。

状态转移方程

• 当 i == j 时，只有一个数字可以选择，dp[i][j] = nums[i]。
• 当 i < j 时，先手玩家有两种选择：
  • 选择 nums[i]，则后手玩家在 nums[i+1...j] 上成为先手，此时先手玩家的得分差为 nums[i] - dp[i+1][j]。
  • 选择 nums[j]，则后手玩家在 nums[i...j-1] 上成为先手，此时先手玩家的得分差为 nums[j] - dp[i][j-1]。