网站机房建设解决方案,申请付费网站,做公司标志用哪个网站,腾讯云网站建设视频教程题目#xff1a;
给一个数组#xff0c;表示纸牌#xff0c;每张纸牌有一定的大小 两个人依次选择左边或者右边的纸牌#xff0c;获得相应的点数 最后点数较大的为胜者 注#xff1a;两个人都是聪明人#xff0c;意味着拿牌会选择让自己获得更多的#xff0c;让对方获得…题目
给一个数组表示纸牌每张纸牌有一定的大小 两个人依次选择左边或者右边的纸牌获得相应的点数 最后点数较大的为胜者 注两个人都是聪明人意味着拿牌会选择让自己获得更多的让对方获得更少的选择 代码如下
//给一个数组表示纸牌每张纸牌有一定的大小
//两个人依次选择左边或者右边的纸牌获得相应的点数
//最后点数较大的为胜者
//注两个人都是聪明人意味着拿牌会选择让自己获得更多的让对方获得更少的选择
#includeiostream
#includealgorithm
using namespace std;
int arr[10000];
int N;
int first1(int L,int R);
int second1(int L,int R);
int first2(int L,int R);
int second2(int L,int R);
int ways2_first[10000][10000];
int ways2_second[10000][10000];
int ways3_first[10000][10000];
int ways3_second[10000][10000];//法一直接递归
int ways1()
{int firstfirst1(0,N-1);int secondsecond1(0,N-1);return max(first,second);
}//先手函数
//先手有两个选择一是拿左边的纸牌则其点数为arr[L]second1(L1,R);二是拿右边的牌则其点数为arr[R]second1(L,R-1)
//而最终的选择是让自己的点数尽可能大所以用max求最大值
int first1(int L,int R)
{if(LR) return arr[L];else{int t1arr[L]second1(L1,R);int t2arr[R]second1(L,R-1);return max(t1,t2);}
}
//后手函数
//后手只能等待对方拿纸牌而对方可以拿左边也可以拿右边的最终对方要让后手拿到的点数尽可能小所以用min函数求最小值
int second1(int L,int R)
{if(LR) return 0;else{int t1first1(L1,R);int t2first1(L,R-1);return min(t1,t2);}
}//法二带有缓存的递归
int ways2()
{//初始化int i,j;for(i0;iN;i)for(j0;jN;j){ //注意这里不要掉了括号因为这个调试了半天ways2_first[i][j]-1;ways2_second[i][j]-1;}int firstfirst2(0,N-1);int secondsecond2(0,N-1);return max(first,second);
}int first2(int L,int R)
{int ans0;if(ways2_first[L][R]!-1) return ways2_first[L][R];else{if(LR) ansarr[L];else{int t1arr[L]second2(L1,R);int t2arr[R]second2(L,R-1);ansmax(t1,t2);}ways2_first[L][R]ans;}return ans;
}int second2(int L,int R)
{int ans0;if(ways2_second[L][R]!-1) return ways2_second[L][R];else{if(LR) ans0;else{int t1first2(L1,R);int t2first2(L,R-1);ansmin(t1,t2);}ways2_second[L][R]ans;}return ans;
}//法三动态规划
int ways3()
{int i;for(i0;iN;i){ways3_first[i][i]arr[i];ways3_second[i][i]0;}for(int startcol1;startcolN;startcol){ int L0;int Rstartcol;while(RN){ways3_first[L][R]max(arr[R]ways3_second[L][R-1],arr[L]ways3_second[L1][R]);ways3_second[L][R]min(ways3_first[L][R-1],ways3_first[L1][R]);L;R;}}return max(ways3_first[0][N-1],ways3_second[0][N-1]);
}int main()
{int choice0;do{cout请输入数组长度:endl;cinN;int i0;cout请输入数组中每个数的值endl;for(i0;iN;i) cinarr[i];int result1ways1();cout法一 直接递归 的结果为 result1endl;int result2ways2();cout法二 缓存递归 的结果为 result2endl;int result3ways3();cout法三 动态规划 的结果为 result3endl;cout继续请输入1endl;cinchoice;}while(choice1);return 0;
}
参考资料
bilibili 马士兵教育——左程云
【应B友要求火速上线算法大神左程云教你从暴力递归到动态规划吊打所有暴力递归、动态规划问题】https://www.bilibili.com/video/BV1ET4y1U7T6?p13vd_source4e9b7dd8105df854ae96830c97920252
