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

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


相关推荐

  • RocketMQ和Kafka应用场景与选型[通俗易懂]

    RocketMQ和Kafka应用场景与选型[通俗易懂]1、适用场景kafka适合日志处理rocketmq适合业务处理结论:两者没有区别,根据具体业务定夺2、性能kafka单机写入TPS号称在百万条/秒rocketmq大约在10万条/秒结论:追求性能方面,kafka单机性能更高3、可靠性kafka使用异步刷盘方式,异步Replicationrocketmq支持异步/同步刷盘,异步/同步Replication结论:rocketmq所支持的同步方式提升了数据的可靠性4、实时性kafka和rocketmq均支持pull长轮询,rocketmq

    2022年10月14日
  • outputstream的子类_java里input

    outputstream的子类_java里inputJavaInputStream类在本教程中,我们将通过一个示例来学习JavaInputStream类及其方法。java.io包的InputStream类是一个抽象超类,它表示字节的输入流。由于InputStream是抽象类,因此它本身没有用。但是,其子类可用于读取数据。InputStream的子类为了使用的InputStream功能,我们可以使用其子类。它的子类有:在下一个教程中,我们将学习…

  • 网站用户单点登录系统

    1背景
      在网站建设的过程中,多个应用系统一般是在不同的时期开发完成的。各应用系统由于功能侧重、设计方法和开发技术有所不同,也就形成了各自独立的用户库和用户认证体系。随着网站的发展,会出现这样的用户群体:以其中的一个用户为例,他(她)使用网站的多个应用系统,但在每个应用系统中有独立的账号,没有一个整体上的网站用户账号的概念,进入每一个应用系统前都需要以该应用系统的账号来登录。这带给用户不方便的使用感受,用户会想:既然我使用的是同一个网站上的应用,为什么不能在一次在网站上

  • python支持向量机回归_支持向量机——核函数与支持向量回归(附Python代码)[通俗易懂]

    python支持向量机回归_支持向量机——核函数与支持向量回归(附Python代码)[通俗易懂]上期跟大家介绍了支持向量机的一般原理,今天继续跟大家聊聊支持向量机——核函数与支持项链回归。1核函数数据通过某种变换,使原本二维的问题通过某种函数转换到高维的特征空间,而这个函数就称为核函数。核函数有很多种,有线性核函数,多项式核函数,高斯核函数等,其中高斯核函数最为著名。核函数可以说是支持向量机的灵魂,因为现实生活中,我们不大可能通过一个线性的等式就可以完美的解决一个分类问题,总是要经过核函数…

  • Javascript注释规范

    Javascript注释规范Javascript注释规范

    2022年10月27日
  • bootstrap-datepicker使用

    bootstrap-datepicker使用

发表回复

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

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