题目描述：给定一个非负的积分数组，玩家1可以从数组两端任取一个积分，接着玩家2执行同样的操作，直至积分被取尽，总分大的获胜。两人都以最优决策进行游戏。对每个数组输出玩家1是否能获胜。

解法1：

使用递归，两者依次取数。

 

class Solution{public:bool PredictTheWinner(vector
     
      & nums){
    return dfs(nums, 0, nums.size()-1, 0, 0, 0);    }    bool dfs(vector
      
       & nums, int st, int en, int p1, int p2, bool role){        if(st == en){
                if(!role && p1+nums[st]>=p2)                return true;            else if(role && p1
      
     

 

 

 

解法二：官方题解

对于两个玩家而言，玩家1的总分s1，玩家2的总分s2，dis=s1-s2，若玩家1胜，dis>=0，否则dis<0。依旧使用递归，双方依次取数，玩家1希望差值越大越好，玩家2希望差值越小越好。

int dfs(vector
    
     & nums, int st, int en, bool role) 函数返回值为：在nums[st,en]上由role取数后的总分差值dis。
    

class Solution{public:bool PredictTheWinner(vector
     
      & nums){
    return dfs(nums, 0, nums.size()-1, 0)>=0;    }    int dfs(vector
      
       & nums, int st, int en, bool role){        if(st == en){            if(role == 0)                return nums[st];            else                return -nums[st];        }        if(!role)            return max(nums[st] + dfs(nums, st+1, en, !role), nums[en]+dfs(nums, st, en-1, !role));        else            return min(-nums[st] + dfs(nums, st+1, en, !role), -nums[en]+dfs(nums, st, en-1, !role));    }};
      
     

 

解法三：官方题解，动态规划

dp[st][en]：玩家1在nums[st,en]上取数过后的差值dis(dis=s1-s2)

在nums[st][en]上的dis: dp[st][en]取决于{num[st], dp[st+1][en]}和{num[en], dp[st][en-1]}，即仅取决于nums[st][en]子数组上的dp和num[st],num[en]。

class Solution{public:    bool PredictTheWinner(vector
     
      & nums){        int dp[25][25];        memset(dp,0,sizeof(dp));        for(int tail=1; tail
      
       =0; head--){                int get_head = nums[head] - dp[head+1][tail];                int get_tail = nums[tail] - dp[head][tail-1];                dp[head][tail] = max(get_head, get_tail);            }        return dp[0][nums.size()-1]>=0;    }};