网站上推广游戏怎么做,网站建设资金筹措的方案,成都营销型网站制作,公司架设网站费用怎么做分录剑指 Offer#xff08;第2版#xff09;面试题 10#xff1a;斐波那契数列 剑指 Offer#xff08;第2版#xff09;面试题 10#xff1a;斐波那契数列解法1#xff1a;递归解法2#xff1a;动态规划解法3#xff1a;动态规划 - 空间优化 剑指 Offer#xff08;第2版第2版面试题 10斐波那契数列 剑指 Offer第2版面试题 10斐波那契数列解法1递归解法2动态规划解法3动态规划 - 空间优化 剑指 Offer第2版面试题 10斐波那契数列
题目来源21. 斐波那契数列
解法1递归
代码
class Solution {
public:int Fibonacci(int n) {if(n 0) return 0;if(n 1) return 1;return Fibonacci(n-1) Fibonacci(n-2);}
};复杂度分析
时间复杂度O(n)。
空间复杂度O(n)。
解法2动态规划
代码
class Solution {
public:int Fibonacci(int n) {vectorint dp(n1, 0);dp[1] 1;for(int i2;in;i)dp[i] dp[i-1]dp[i-2];return dp[n];}
};复杂度分析
时间复杂度O(n)。
空间复杂度O(n)。
解法3动态规划 - 空间优化
用 3 个变量就能代替之前的动态规划数组。
代码
class Solution {
public:int Fibonacci(int n) {int first 0, second 1;while(n--){int res first second;first second;second res;}return first;}
};复杂度分析
时间复杂度O(n)。
空间复杂度O(1)。
