题目来源:https://leetcode.cn/problems/fibonacci-number/description/
C++题解1:根据题意,直接用递归函数。
class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
else if(n == 1) return 1;
else return(fib(n-1) + fib(n-2));
}
};
C++题解2(来源代码随想录):动态规划。动规五部曲:这里我们要用一个一维dp数组来保存递归的结果。文章来源:https://www.toymoban.com/news/detail-618241.html
- 确定dp数组以及下标的含义:dp[i]的定义为第i个数的斐波那契数值是dp[i]
- 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
- dp数组如何初始化:dp[0] = 0; dp[1] = 1;
- 确定遍历顺序:从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的
- 举例推导dp数组:按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55
- 时间复杂度:O(n)
- 空间复杂度:O(n)
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};
C++题解3(来源代码随想录):动态规划。只需要维护两个数值就可以了,不需要记录整个序列。文章来源地址https://www.toymoban.com/news/detail-618241.html
- 时间复杂度:O(n)
- 空间复杂度:O(1)
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
到了这里,关于力扣 509. 斐波那契数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!