爱站网影视排行榜,网络规划设计师难考吗,外贸网页设计公司,网页游戏排行榜13文章目录 一、题目二、递归#xff0c;动态规划解法2.1 递归解法2.2 动态规划解法 三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、递归#xff0c;动态规划解法
2.1 递归解法 思路分析#xff1a;斐波… 文章目录 一、题目二、递归动态规划解法2.1 递归解法2.2 动态规划解法 三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、递归动态规划解法
2.1 递归解法 思路分析斐波那契数列可以用递归实现下面直接给出代码非常简单。递归的代码简单但是递归的速度很慢因为递归代码中的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 程序如下
class Solution {
public:int fib(int n) { // 1 1 2 3 5 8 13 21if (n 1) return n;return fib(n - 1) fib(n - 2);}
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)一个fib(n)时间复杂度为 O ( ( 1 n ) ∗ n / 2 ) O ( n 2 ) O((1n)*n/2)O(n^2) O((1n)∗n/2)O(n2)。空间复杂度 O ( n ) O(n) O(n)递归中栈所需的空间。
2.2 动态规划解法 思路分析动态数组为 d p [ i ] d p [ i − 1 ] d p [ i − 2 ] dp[i] dp[i - 1] dp[i - 2] dp[i]dp[i−1]dp[i−2]根据此公式写出如下代码。 程序如下
class Solution {
public:int fib(int n) { // 1 1 2 3 5 8 13 21if (n 1) return n;vectorint dp(n 1); // 动态规划中的dp数组dp[0] 0;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。 但是实际上我们可以看到计算斐波那契数列只需要用到两个值不必保留整个动态数组。因此对上述代码进行内存优化空间复杂度从 O ( n ) O(n) O(n)变成 O ( 1 ) O(1) O(1)。
class Solution {
public:int fib(int n) { // 1 1 2 3 5 8 13 21if (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];}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
三、完整代码
# include iostream
# include vector
using namespace std;//class Solution {
//public:
// int fib(int n) { // 1 1 2 3 5 8 13 21
// if (n 1) return n;
// return fib(n - 1) fib(n - 2);
// }
//};//class Solution {
//public:
// int fib(int n) { // 1 1 2 3 5 8 13 21
// if (n 1) return n;
// vectorint dp(n 1); // 动态规划中的dp数组
// dp[0] 0;
// dp[1] 1;
// for (int i 2; i n; i) {
// dp[i] dp[i - 1] dp[i - 2];
// }
// return dp[n];
// }
//};class Solution {
public:int fib(int n) { // 1 1 2 3 5 8 13 21if (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];}
};int main() {int n 4;Solution s1;int result s1.fib(n);cout result endl;system(pause);return 0;
}end
