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

2024-01-24 00:20

本文主要是介绍动态规划学习——赢得最大数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

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

代码如下:

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

这篇关于动态规划学习——赢得最大数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/637994

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示