递归迭代动态规划「建议收藏」

递归迭代动态规划「建议收藏」一、定义递归:程序调用自身,从顶部将问题分解,其问题与其子问题是同一概念。通过解决掉所有分解出来的小问题,来解决整个问题。迭代:利用变量的原值推算出变量的下一个值。递归中一定有迭代,但是迭代中不一定有递归。动态规划:通常与递归相反,其从底部开始解决问题。将所有小问题解决掉,进而解决的整个问题。为了节约重复求相同子问题的时间,引入一个数组,把所有子问题的解存于该数组中,动态规划算法是空间换时间的算法。动态规划可以递归地实现,也可以非递归(循环的方法)地实现。运行速度:动态规划>迭代&gt

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

一、定义

递归:程序调用自身,从顶部将问题分解,其问题与其子问题是同一概念。通过解决掉所有分解出来的小问题,来解决整个问题。

迭代:利用变量的原值推算出变量的下一个值。递归中一定有迭代,但是迭代中不一定有递归。

动态规划:通常与递归相反,其从底部开始解决问题。将所有小问题解决掉,进而解决的整个问题。为了节约重复求相同子问题的时间,引入一个数组,把所有子问题的解存于该数组中,动态规划算法是空间换时间的算法。

动态规划可以递归地实现,也可以非递归(循环的方法)地实现。

运行速度:动态规划 > 迭代 > 递归

二、递归

递归有两个特点:

1)函数自身调用自身;

2)使用递归时必须要有一个明确的出口;

递归分两个阶段:

1)递推:把复杂的问题推到比原问题简单的子问题的求解;

2)回归:当获取最简单的情况后,逐步返回,依次得到复杂问题的解;

int fibonacci(int n)
{
	if (n <= 2)
		return 1;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);
}

Jetbrains全家桶1年46,售后保障稳定

三、迭代

由第一个数和第二个数去求解第三个数,由第二个数和第三个数去求解第四个数,以此类推。

int fibonacci(int n)
{
	if (n <= 2)
		return 1;
		
	int first = 1, second = 1, answer;
	for (int i = 3; i <= n; i++)
	{
		answer = first + second;
		first = second;
		second = answer;
	}
	
	return answer;
}

四、动态规划

子问题的解存储在一张表格里,这样每个子问题只用计算一次。但是需要额外的空间以节省时间。

int fibonacci(int n)
{
	vector <int> dp;
	dp.push_back(0);
	dp.push_back(1);
 
	for (int i = 3; i <= n; i++)
		dp.push_back(dp[i-1] + dp[i-2]);
 
	return dp[n];
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/222959.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号