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