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

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

头像
KEY.L
编辑于 07-07 08:35 APP内打开
赞 26 | 收藏 53 | 回复18 | 浏览1656
之前刷题目的时候,最头疼的就是动态规划类型的题目了,一开始一点思绪想法都没有
想看数学题一样痛苦不堪 而且一点同情都没有,数学题起码还有选择题可以蒙,这蒙也蒙不了
勉强哗啦啦打个暴力上去一测,好家伙只有几个可怜的样例点过了
那么动态规划为啥那么难呢?
先上一段百度百科对 动态规划的解释
动态规划 (Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程 最优化的过程。20世纪50年代初,美国 数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理 ,从而创立了动态规划动态规划的应用极其广泛,包括工程技术 、经济、工业生产、军事以及自动化控制 等领域,并在背包问题 、生产经营问题、资金管理问题、资源分配问题 最短路径问题 和复杂系统可靠性问题等中取得了显著的效果
简单来说就是对于多个阶段决策过程中的最优化思想
这样听是不是有点头疼?
先上个开胃小菜~~~

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

我第一次看这个题的时候被难成傻der了~~~,不过其实可以把他当做一个简单的小学数学题做(确信) 🤣
那就先讲小学做法吧(hhh)
第一种解法 通过 枚举 3的个数,当你已知3的个数就可以求出2的个数,以此类推,3的个数确定,2的个数也可以确定,剩下的就是1啦~~~~ 假设3的个数为i(0<=i<=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。



更多模拟面试

8条回帖

回帖
加载中...
话题 回帖

近期热帖

近期精华帖

热门推荐