<h3><a title="题目描述" href="https://leetcode-cn.com/problems/predict-the-winner/">题目描述</a></h3>  <h4>方法一</h4> <pre class="EnlighterJSRAW" data-enlighter-language="python">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] for i in range(n-2,-1,-1): for j in range(i+1,n): dp[i][j]=max(nums[j]-dp[i][j-1],nums[i]-dp[i+1][j]) return dp[0][-1]>=0 </pre> <p> </p> ## 思路： 这里我们定义dp[i][j]为[i,j]中玩家1比玩家2最多能获得的分数 首先直观可知dp[i][i]=nums[i]. [i,j]区间内玩家有两种操作方式： 1.先拿nums[j]，玩家1获得了nums[j].此时dp[i][j-1]就是玩家2比玩家1最多能获得的分数,此时玩家1比玩家2最多能获得的分数就是nums[j]-dp[i][j-1] 2.先拿nums[i]，玩家1获得了nums[i].此时dp[i+1][j]就是玩家2比玩家1最多能获得的分数,此时玩家1比玩家2最多能获得的分数就是nums[i]-dp[i+1][j] 所以：dp[i][j]=max(nums[j]-dp[i][j-1],nums[i]-dp[i+1][j]) 判断dp[0][-1]与0的大小就可知玩家1是否获胜。