预测赢家-暴力递归法

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

假设每个玩家的玩法都会使他的分数最大化，输出赢家分数。

#include <iostream>
#include <vector>
using namespace std;

int g(vector<int>& vec,int left,int right);
int f(vector<int>& vec,int left,int right){ //先手
    if(left == right){
        return vec[left];
    }
    int p1 = vec[left]+g(vec,left+1,right);
    int p2 = vec[right]+g(vec,left,right-1);
    return max(p1,p2);
}

int g(vector<int>& vec,int left,int right){  //后手
    if(left == right){
        return 0;
    }
    int p1 = f(vec,left+1,right);//先手拿走了l
    int p2 = f(vec,left,right -1);//先手拿走了r
    
    return min(p1,p2); //先手做决定，所以剩下的是较小的分数
}

int win1(vector<int>& vec){//返回获胜者分数
   return max(f(vec,0,vec[vec.size()-1]),g(vec,0,vec[vec.size()-1]));//取先手和后手中最大的
    
}

int main(){
    vector<int>vec{1,100,4,4,5};
    cout<<win1(vec)<<endl;
    return 0;
}