原題地址
https://leetcode.com/problems/predict-the-winner/description/
題意
給定一個數(shù)組鼻疮，玩家1和玩家2依次從數(shù)組的兩端之一取一個數(shù)搜贤，直到取完升略，取出的數(shù)的和最大的玩家獲勝。假設(shè)玩家都按照自己的最優(yōu)策略來取數(shù)通砍，預(yù)測哪個玩家會贏界睁。
思路
一開始我直接想用動態(tài)規(guī)劃的方法做画舌，但是沒想對。
（一開始的想法：覺得和那種一次跳一步兩步然后求最小代價路徑的差不多介褥， 用dp[i][0]表示一個玩家第i步的時候取最左端的值能達到的最大值粘优，dp[i][1]表示一個玩家第i步取最右端的值能達到的最大值，而遞推方程是
dp1[i][0] = nums[left] + max(dp1[i - 1][0], dp1[i - 1][1])
dp1[i][1] = nums[right] + max(dp1[i - 1][0], dp1[i - 1][1])）
沒成功于是就先用遞歸的解法做了呻顽，遞歸的解法就好理解很多了雹顺，就是把每一種取值情況都列舉出來然后從里面挑一個玩家1的值最大的（實現(xiàn)里是用玩家1的值減去玩家2的值，因此leftover大于等于0即可）
代碼
遞歸做法
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
if(n<=1) return true;
return leftover(nums,0,n-1)>=0;
}
int leftover(vector<int> & nums, int left,int right){
if(left==right) return nums[right];
return max(nums[left]-leftover(nums,left+1,right), nums[right]-leftover(nums,left,right-1));
}
};
動態(tài)規(guī)劃做法
其他
其實這題好像是課后習題來著廊遍？……（好的我知道你沒聽課了
