题目描述
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
重叠子问题的消除
参考文献
https://www.bilibili.com/video/BV1XV411Y7oE/?spm_id_from=333.999.0.0&vd_source=6d9319d2be5cfbedee56f9fe19a1cfbc
算法1
(暴力递归) $O(2^n)$
blablabla
时间复杂度
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n;
int memo[N];
int fib(int n){
if(n == 1 || n == 2) return 1;
return fib(n-1)+fib(n-2);
}
int main(){
cin >> n;
memset(memo,0,sizeof memo);
cout << fib(n)<<endl;
return 0;
}
图中有重叠部分,涉及到重叠子问题,
根据递归计算f(20)=f(19)+f(18),然后计算f(19)和f(18),f(19)又需要计算f(18)…
如果把已经计算过的数存起来,等需要的时候去查找;
算法2
(备忘录递归) $O(n)$
把已经计算过的数存入“备忘录”memo[N];
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n;
int memo[N];
int helper(int n){
if(n == 0 || n == 1) return n;
if(memo[n] != 0) return memo[n];
memo[n] = helper(n-1) + helper(n-2);
return memo[n];
}
int main(){
cin >> n;
memset(memo,0,sizeof memo);
cout << helper(n)<<endl;
return 0;
}
---------以上都是自顶向下进行递归计算,而常见的动态规划是自底向上
算法3
(dp) $O(n)$
上面都是输入n然后一步一步向下找到最底端递归,如果换成自底向上,一步一步向上求,一边求一边存入表中
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n;
int dp[N];
int fib(int n){
if(n == 0) return 0;
dp[0] = 0;
dp[1] = 1;
//状态转移
for(int i = 2; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main(){
cin >> n;
memset(dp,0,sizeof dp);
cout << fib(n)<<endl;
return 0;
}
状态转移:f(n)的参数不断变化,由n这个状态由n-1和n-2转移(相加)而来
上面的dp就类似于备忘录递归倒过来,
根据状态转移可以看出来斐波拉契数当前状态只和前两个状态有关,
也就是说每次可以只存前两个状态
优化代码 $O(1)$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n;
int fib(int n){
if(n == 0 || n == 1) return n;
//dp[i-1] dp[i-2]
int dp_i_1 = 1;
int dp_i_2 = 0;
int dp_i = 0;
for(int i = 2; i <= n; i++){
dp_i = dp_i_1 + dp_i_2;
//实时更新 dp_i_1 , dp_i_2
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
//两个顺序不能调换
//dp_i_2受当前状态的dp_i_1影响,调换会导致 当前状态dp_i = dp_i_1 = dp_i_2
}
return dp_i;
}
int main(){
cin >> n;
//memset(dp,0,sizeof dp);
cout << fib(n)<<endl;
return 0;
}