写点什么

教你学 c++ 算法题中最头疼的动态规划

作者:KEY.L
  • 2022 年 7 月 04 日
  • 本文字数:1451 字

    阅读完需:约 5 分钟

之前刷题目的时候,最头疼的就是动态规划类型的题目了,一开始一点思绪想法都没有

想看数学题一样痛苦不堪

而且一点同情都没有,数学题起码还有选择题可以蒙,这蒙也蒙不了

勉强哗啦啦打个暴力上去一测,好家伙只有几个可怜的样例点过了

那么动态规划为啥那么难呢?

先上一段百度百科对动态规划的解释

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20 世纪 50 年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果

简单来说就是对于多个阶段决策过程中的最优化思想

这样听是不是有点头疼?

先上个开胃小菜~~~

题意:在一个国家仅有 1 分,2 分,5 分硬币,将 n(n>=5)分钱兑换成硬币有很多种兑法。求有多少种兑换方式。

我第一次看这个题的时候被难成傻 der 了~~~,不过其实可以把他当做一个简单的小学数学题做(确信)🤣

那就先讲小学做法吧(hhh)

第一种解法:通过枚举3 的种类数,当你已知 3 的个数就可以求出 2 的种类,以此类推,3 的个数确定,2 的个数也可以确定,剩下的就是 1 啦~~~~假设 3 的个数为 x(0<=x<=n/3),那么 2 的个数就是


再然后 1 的个数就确定了。

#include<bits/stdc++.h>using namespace std;int  main(){	int n;	while(cin>>n){		int i,j,ans=0;		for(i=0;i<=n/3;i++){			int temp=(n-3*i);     			ans+=temp/2+1;        		}		cout<<ans<<endl;	}}
复制代码

是不是突然一拍脑门,心想就这?那来看看第二种解法吧~

第二种解法:是类似完全背包 dp, 比较经典的 dp 问题,外层循环是硬币的价值,可以一个一个枚举,如果 i=1,那么则一直放 1,求出方案数,其他同理。hhhh 是不是有点难懂了?

#include<bits/stdc++.h>using namespace std;const int maxn=32768+10000;int dp[maxn];int main(){	int n,i,j;	while(~scanf("%d",&n)){		memset(dp,0,sizeof(dp));		dp[0]=1;		for(i=1;i<=3;i++){			for(j=i;j<=n;j++){				dp[j]+=dp[j-i];			}		}		cout<<dp[n]<<endl;	}}
复制代码

那先上一道比较简单而且经典的吧~

m 个苹果放在 n 个盘子里面有多少种放法?(动态规划)

设 f(m,n) 为 m 个苹果,n 个盘子的放法数目,则先对 n 作讨论,如果 n>m,必定有 n-m 个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响;

即 if(n>m) f(m,n) = f(m,m)  当 n<=m 时,不同的放法可以分成两类:即有至少一个盘子空着或者所有盘子都有苹果,前一种情况相当于 f(m,n) = f(m,n-1);

后一种情况可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即 f(m,n) = f(m-n,n).

而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)。边界条件为 m=0 或 n=1 时,只有一种放法。

#include<bits/stdc++.h>using namespace std;int fun(int m,int n){	if(m==0||n==1)		return 1;	if(m<n)		return fun(m,m);	else		return fun(m,n-1)+fun(m-n,n);	}int main(){	int m,n,t;	cin>>t;	while(t--){		cin>>m>>n;		cout<<fun(m,n)<<endl;	}	return 0;}
复制代码

全部看完之后,是不是觉得自己 dp 已经小成了~~~~

最后上一道家庭作业 hhhh 很久之前的 HDU 的题了

稍微讲一下思路吧~从终点判,蜜蜂每次只能从前 1 个蜂房或者前 2 个蜂房过来所以:dp[i]=dp[i-1]+dp[i-2];再数出终点和起点相差的格子数为 b-a+1,记得开 longlong。


用户头像

KEY.L

关注

还未添加个人签名 2022.07.01 加入

还未添加个人简介

评论

发布
暂无评论
教你学c++算法题中最头疼的动态规划_KEY.L_InfoQ写作社区