力扣486 預測赢家

1、遞歸

https://leetcode-cn.com/problems/predict-the-winner/solution/yu-ce-ying-jia-by-leetcode-solution/

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        if(nums.size()%2 == 0)return true;
        return dfs(nums,0,nums.size()-1,1)>=0;
    }
    int dfs(vector<int>& nums,int start,int end,int trun)
    {
        if(start == end)
        {
            return nums[start]*trun;//遞歸條件
        }
        int startdfs = nums[start]*trun + dfs(nums,start+1,end,-trun);
        int enddfs = nums[end]*trun + dfs(nums,start,end-1,-trun);
        return max(startdfs*trun,enddfs*trun)*trun;傳回出口
    }
};