动态规划学习——赢得最大数

发布时间:2024年01月23日

题目:

给一个数组,表示纸牌,每张纸牌有一定的大小
两个人依次选择左边或者右边的纸牌,获得相应的点数
最后点数较大的为胜者
注:两个人都是聪明人,意味着拿牌会选择让自己获得更多的,让对方获得更少的选择

代码如下:

//给一个数组,表示纸牌,每张纸牌有一定的大小
//两个人依次选择左边或者右边的纸牌,获得相应的点数
//最后点数较大的为胜者
//注:两个人都是聪明人,意味着拿牌会选择让自己获得更多的,让对方获得更少的选择
#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

文章来源:https://blog.csdn.net/qq_39991776/article/details/135796163
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。