C++之动态规划(动态规划入门)

C++之动态规划(动态规划入门),第1张

C++之动态规划(动态规划入门)

今天这篇文章,我们来谈一谈算法中的一种思想————动态规划。

可能有些读者有接触过动态规划,可能也有一些读者以前完全不知道动态规划这个东西,别担心,我这篇文章会为读者做一个入门,好让读者掌握这个重要的知识点。

首先,读者需要知道,动态规划实质上是一种思想,并不是以中具体的算法,在面对某些问题的啥时候,我们可以利用动态规划这个思想将问题转化,从而达到解决问题的地步。

补充一点:动态规划简称dp(全称dynamic programming)

我们通过一下三个问题来了解动态规划。

问题一:现在有一个n阶的台阶,你一次只能上一步或两步,请问你到第n阶台阶的方法数有多少?这个问题算是动态规划中最简单的问题了,读者可以自己先思考一会,然后在看解析。

首先,我们来分析一下问题,其实不难发现,我们假设到达第n阶台阶的方法数位dp [n], 那么事实上到达第n阶的方法数就等于到达n - 1阶的方法数加上到达n - 2阶的方法数,所以我们就可以就可以写出关系式 dp[n] = dp[n - 1] + dp[n - 2] 。这个关系式我们把它叫做动态转移方程,可能有眼尖的读者已经可以发现,这不就是数学上的递推式吗?如果你能看出来,那么恭喜你,你很有潜质!

此题的代码实现如下:

#include 
using namespace std;
int dp[100] = { 1,1 };
int main()
{
	int n;//n表示台阶数
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		dp[n] = dp[n - 1] + dp[n - 2];
	}
	cout << dp[n];
	return 0;
}

如果这道题没有运用动态规划的思想,那么正常思考难度极大,但是我们运用动态规划思想,就轻松的将问题迎刃而解了。

问题二:相信大家已经很熟悉汉诺塔问题了,但是这次的问题是,有n个盘子,求把盘子从A针移到C针的方法数。

这道题我们这样思考,我们首先需要三个步骤

1:将n - 1个盘子从A针移到B针(通过C针)

2:将一个盘子从A针移到C针

3:将n - 1个盘子从B针移到C针(通过A针)

我们定义dp[n] 为将n个盘子从一个针移到另外一个针的方法数

那么原问题就会变成:

1:将n - 1个盘子从A针移到B针(通过C针)(有dp[n - 1]钟方法)

2:将一个盘子从A针移到C针 (有一种方法)

3:将n - 1个盘子从B针移到C针(通过A针) (有dp[n - 1]钟方法)

通过上述分析,我们就可以写出这道题的动态转移方程:dp[n] = 2 * dp[n - 1] + 1

所以,我们就可以码出代码,本题代码实现如下:

#include 
using namespace std;
#define max 100
int dp[max] = {0,1};
int main()
{
	int n; //n代表有几个碟子
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = 2 * dp[i - 1] + 1;
	}
	cout << dp[n];
	return 0;
}

这题也是一样,正常去思考难度极大,但是通过动态规划,我们也是将问题迎刃而解了。

相信看到这里,读者已经对动态规划有了一定的了解,接下来这题将是本文的最后一道例题,同时也是最难的一道。

题目:现在假设:你有足够的长度分别为1,2,3,……,n的长条积木,你有多少种搭出高度为h的上升三角塔(每个积木横着放,高度都为1)”
解释:积木横着搭高,上面的积木长度不得大于下面的积木,例如高度为4,从上往下积木的长度分别为1223和1234为上升三角塔,但1232不是上升三角塔。

输入要求:只有一行包括两个正整数n, h(0< n < 40, 0 < h < 40),n代表长条积木的长度分别为1,2,3,……,n,h代表要搭出的高度
注意:每个长度(1,2,3,……,n)的积木的数量都是充足的,不用担心不够搭。
保证答案能用long long存下。

输出要求:输出一行包括一个正整数,代表方案数

输入样例:3 3

输出样例 10

提示:

对于第一个样例,10种分别为
111
112
113
122
123
133
222
223
233
333

仔细读完题目后,可能读者回想用穷举法来实现,因为我可以一一列举,但事实上,这题是没有办法用列举法实现的,因为高度和长度都是未知的,但是我们编写的程序又是有界的,所以没办法用列举法,但是本题的难点就在于分析出它是一个动态规划问题。

我们这样去思考,在排列过程中,我们不难发现,第m层长度为k的方法数为第m - 1层从长度为k到n的累加,当h = 1时(高度为1),这时候我们的方法数就是n。

通过以上分析,我们就可以写出其对应的动态转移方程。

我们定义,第m层长度为k时的方法数为dp[m][k]。

此时就会有dp[m][k] = dp[m - 1][ k ] + dp[m - 1][k + 1] + .... + dp[m - 1] [n]

 求完每层长度为k的方法数之后,我们再将其全部累加之后就是我们所要的答案

代码实现如下:

#include 
using namespace std;
long long dp[50][50];
long long sum = 0;
int main()
{
	int n, h;
	cin >> n >> h;
	for (int i = 1; i < 49; i++)
	{
		dp[1][i] = 1;
		for (int k = 1; k < 49; k++)
			dp[i + 1][k] = 0;
	}
	for (int m = 2; m <= h; m++)
	{
		for (int j = 2; j <= n; j++)
		{
			for (int k = j; k <= n; k++)
			{
				dp[m][j] += dp[m - 1][k];
			}
		}
	}
	for (int m = 1; m <= h; m++)
	{
		for (int k = 1; k <= n; k++)
		{
			sum += dp[m][k];
		}
	}
	cout << sum;
	return 0;
}

好了,以上就是本文的全部内容了。

回顾一下,本文浅谈动态规划思想,在解决某些问题是堪称神器,但是难点在于如何去分析该问题为一个动态规划问题,本文所写的还不能让读者可以完全掌握动态规划(因为作者也学了没多久换哈哈哈)但主要还是给读者做一个入门,让读者可以先了解一下动态规划是什么,这也是我写这篇文章的初衷,谢谢。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5097286.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-16
下一篇 2022-11-16

发表评论

登录后才能评论

评论列表(0条)

保存