本文主要是介绍动态规划学习——赢得最大数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给一个数组，表示纸牌，每张纸牌有一定的大小
两个人依次选择左边或者右边的纸牌，获得相应的点数
最后点数较大的为胜者
注：两个人都是聪明人，意味着拿牌会选择让自己获得更多的，让对方获得更少的选择
代码如下：
//给一个数组，表示纸牌，每张纸牌有一定的大小
//两个人依次选择左边或者右边的纸牌，获得相应的点数
//最后点数较大的为胜者
//注：两个人都是聪明人，意味着拿牌会选择让自己获得更多的，让对方获得更少的选择
#include<iostream>
#include<algorithm>
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 first=first1(0,N-1);int second=second1(0,N-1);return max(first,second);
}//先手函数
//先手有两个选择，一是拿左边的纸牌，则其点数为arr[L]+second1(L+1,R);二是拿右边的牌，则其点数为arr[R]+second1(L,R-1)
//而最终的选择是让自己的点数尽可能大，所以用max求最大值
int first1(int L,int R)
{if(L==R) return arr[L];else{int t1=arr[L]+second1(L+1,R);int t2=arr[R]+second1(L,R-1);return max(t1,t2);}
}
//后手函数
//后手只能等待对方拿纸牌，而对方可以拿左边也可以拿右边的，最终对方要让后手拿到的点数尽可能小，所以用min函数求最小值
int second1(int L,int R)
{if(L==R) return 0;else{int t1=first1(L+1,R);int t2=first1(L,R-1);return min(t1,t2);}
}//法二：带有缓存的递归
int ways2()
{//初始化int i,j;for(i=0;i<=N;i++)for(j=0;j<=N;j++){ //注意这里不要掉了括号，因为这个调试了半天ways2_first[i][j]=-1;ways2_second[i][j]=-1;}int first=first2(0,N-1);int second=second2(0,N-1);return max(first,second);
}int first2(int L,int R)
{int ans=0;if(ways2_first[L][R]!=-1) return ways2_first[L][R];else{if(L==R) ans=arr[L];else{int t1=arr[L]+second2(L+1,R);int t2=arr[R]+second2(L,R-1);ans=max(t1,t2);}ways2_first[L][R]=ans;}return ans;
}int second2(int L,int R)
{int ans=0;if(ways2_second[L][R]!=-1) return ways2_second[L][R];else{if(L==R) ans=0;else{int t1=first2(L+1,R);int t2=first2(L,R-1);ans=min(t1,t2);}ways2_second[L][R]=ans;}return ans;
}//法三：动态规划
int ways3()
{int i;for(i=0;i<N;i++){ways3_first[i][i]=arr[i];ways3_second[i][i]=0;}for(int startcol=1;startcol<N;startcol++){ int L=0;int R=startcol;while(R<N){ways3_first[L][R]=max(arr[R]+ways3_second[L][R-1],arr[L]+ways3_second[L+1][R]);ways3_second[L][R]=min(ways3_first[L][R-1],ways3_first[L+1][R]);L++;R++;}}return max(ways3_first[0][N-1],ways3_second[0][N-1]);
}int main()
{int choice=0;do{cout<<"请输入数组长度:"<<endl;cin>>N;int i=0;cout<<"请输入数组中每个数的值"<<endl;for(i=0;i<N;i++) cin>>arr[i];int result1=ways1();cout<<"法一 直接递归 的结果为 "<<result1<<endl;int result2=ways2();cout<<"法二 缓存递归 的结果为 "<<result2<<endl;int result3=ways3();cout<<"法三 动态规划 的结果为 "<<result3<<endl;cout<<"继续请输入1"<<endl;cin>>choice;}while(choice==1);return 0;
}参考资料：
bilibili 马士兵教育——左程云
【应B友要求火速上线！算法大神（左程云）教你从暴力递归到动态规划，吊打所有暴力递归、动态规划问题】https://www.bilibili.com/video/BV1ET4y1U7T6?p=13&vd_source=4e9b7dd8105df854ae96830c97920252
这篇关于动态规划学习——赢得最大数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
