leetcode 486. Predict the Winner

原题地址

https://leetcode.com/problems/predict-the-winner/description/

题意

给定一个数组，玩家1和玩家2依次从数组的两端之一取一个数，直到取完，取出的数的和最大的玩家获胜。假设玩家都按照自己的最优策略来取数，预测哪个玩家会赢。

思路

一开始我直接想用动态规划的方法做，但是没想对。
（一开始的想法：觉得和那种一次跳一步两步然后求最小代价路径的差不多， 用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的值最大的（实现里是用玩家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));
    }
};

动态规划做法

其他

其实这题好像是课后习题来着？……（好的我知道你没听课了