用三种方法实现:

1. 带备忘录的递归
2. dp迭代
3. 迭代优化，空间复杂度为O(1)

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

#define _for(i,a,b) for(int i=(a);i<=(b);i++)

//备忘录
int helper(vector<int>& memo, int n) {
	//base case
	if (n == 2 || n == 3) {
		return 1;
	}
	if (memo[n] != 0) {
		return memo[n];
	}
	else {
		memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
		return memo[n];
	}
}

//带备忘录法
int fib_1(int N) {
	if (N <= 1) {
		return 0;
	}
	vector<int> memo(N + 1, 0);
	return helper(memo, N);
}

//dp数组迭代法
int fib_2(int N) {
	vector<int> dp(N + 1, 0);
	dp[1] = 0;
	dp[2] = dp[3] = 1;
	_for(i, 4, N) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[N];
}

//迭代优化
int fib_3(int N) {
	if (N == 1) {
		return 0;
	}
	if (N == 2 || N == 3) {
		return 1;
	}
	int pre = 1, ppre = 1;
	_for(i, 4, N) {
		int sum = pre + ppre;
		ppre = pre;
		pre = sum;
	}
	return pre;
}

int main()
{
	printf("%d", fib_3(10));
}