预测赢家-暴力递归法
给你一个整数数组 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;
}
查看12道真题和解析
