leetcode_cpp/fbl.cpp
2021-12-22 13:23:43 +08:00

60 lines
1.2 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/*
* @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;
}