大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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];
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222959.html原文链接：https://javaforall.net
