60 lines
1.2 KiB
C++
60 lines
1.2 KiB
C++
/*
|
||
* @Description:
|
||
* @Version: 1.0
|
||
* @Autor: zhuyijun
|
||
* @Date: 2021-11-10 21:56:48
|
||
* @LastEditTime: 2021-11-28 10:49:53
|
||
*/
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
int fbl1(int n) {
|
||
if (n == 1 || n == 2) return 1;
|
||
return fbl1(n - 1) + fbl1(n - 2);
|
||
}
|
||
|
||
int helper(vector<int> list, int n) {
|
||
if (n == 1 || n == 2) {
|
||
return 1;
|
||
}
|
||
//判断该n是否已经计算过,如果不等于0则已经计算过 获取其值
|
||
if (list[n] != 0) return list[n];
|
||
list[n] = helper(list, n - 1) + helper(list, n - 2);
|
||
return list[n];
|
||
}
|
||
int fbl(int n) {
|
||
//维护一个备忘录 倍计算过的值都会被记录到里面
|
||
vector<int> list(n + 1, 0);
|
||
return helper(list, n);
|
||
}
|
||
// dp方法 1
|
||
int fbl_dp(int n) {
|
||
vector<int> dp(n + 1, 0);
|
||
dp[1] = dp[2] = 1;
|
||
for (int i = 3; i <= n; i++) {
|
||
dp[i] = dp[i - 1] + dp[i - 2];
|
||
}
|
||
return dp[n];
|
||
}
|
||
|
||
// dp 优化
|
||
int fbl_dp2(int n) {
|
||
if (n == 1 || n == 2) {
|
||
return 1;
|
||
}
|
||
int prev = 1, curr = 1;
|
||
for (int i = 3; i <= n; i++) {
|
||
int sum = prev + curr;
|
||
prev = curr;
|
||
curr = sum;
|
||
}
|
||
return curr;
|
||
}
|
||
int main() {
|
||
std::cout << fbl(5) << std::endl;
|
||
std::cout << fbl1(5) << std::endl;
|
||
std::cout << fbl_dp(5) << std::endl;
|
||
std::cout << fbl_dp2(5) << std::endl;
|
||
|
||
return 0;
|
||
} |