486.predict-the-winner.md

486. 预测赢家

1. 描述

   • 给定一个非负整数数组, 表示 score.
   • 规则
     • 玩家 1 (先手)从数组任意一端拿取一个score，
     • 玩家2(后手) 继续从剩余数组任意一端拿取score，
     • 玩家 1 拿，…… 。
   • 最终, score总和最多的玩家获胜。
   • 注：
     • 每次只能从数组的任意一端拿取数字
     • 如果最终 两个score相等，那么玩家 1 仍为赢家

2. 思路

   • 为了判断哪个玩家可以获胜，

     • 可以计算 先手得分 与 后手得分之差。
     • 当数组中的所有数字都被拿取时，如果总分 >= 0，则先手获胜，反之则后手获胜。

   • 为了 记录当前玩家是先手/后手，

     • 记录 当前玩家的得分 记为正/负

   • 两种方法：递归、DP。

   • i表示左端点，j表示右端点。

   • 为了表示 先手玩家1 在数组[i:j]中，赢过对方的分数差值，定义:

     • 递归函数 dfs(i,j)
     • dp[i][j]：
       • 假如玩家1先取左端 nums[i]，玩家2能赢对方的差值就是dp[i+1][j]
       • 如果玩家1先取右端 nums[j]，玩家2能赢对方的差值就是dp[i][j-1]

   • 当 i == j，即只剩一个score，玩家只能拿这个了。

     • 递归的终止条件（见代码）
     • DP base case：当i == j时，dp[i][j] = nums[i]。

   • 递归函数 和 DP状态转移方程

     • 递归函数dfs(i,j) return 的是：
       • Max(nums[i] - dfs(i+1, j), nums[j] - dfs(i, j-1))
     • DP 状态转移方程：
       • dp[i][j] = Max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
       • 注意，由于 i <= j，所以只用填半张表。
       • 状态转移的方向，如图
         • 
         • 

3. 实现

   • 方法一：递归

     class Solution {
     public:
         int dfs(vector<int>& nums, int i, int j) {
             if (i == j)
                 return nums[i];
     
             int pickLeft = nums[i] - dfs(nums, i + 1, j);
             int pickRight = nums[j] - dfs(nums, i, j - 1);
             return max(pickLeft, pickRight);
         }
     
         bool PredictTheWinner(vector<int>& nums) {
             return dfs(nums, 0, nums.size() - 1) >= 0 ;
         }
     };
     

   • 方法二

     class Solution {
     public:            
         bool PredictTheWinner(vector<int>& nums) {
             int i, j;
             vector<vector<int>>dp(nums.size(), vector<int>(nums.size(), 0));
             for(i=0; i<nums.size(); i++)
                 dp[i][i] = nums[i];
     
             for(i=nums.size()-2; i>=0; i--)
                 for(j=i+1; j<nums.size(); j++)
                 {
                     int pickLeft  = nums[i] - dp [i + 1][j];
                     int pickRight = nums[j] - dp [i][j - 1];
                     dp[i][j] = max(pickLeft, pickRight);
                 }
     
             return dp[0][nums.size()-1] >= 0 ;
         }
     };
     

4. 参考