大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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);
}
三、迭代
由第一个数和第二个数去求解第三个数,由第二个数和第三个数去求解第四个数,以此类推。
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账号...