题解 | #N阶楼梯上楼问题#

#include<iostream>
#include<vector>
using namespace std;
//传统递归
int Fibonacci(int n) {
	if (n == 1 || n == 2) {
		return n;
	}
	else return Fibonacci(n - 1) + Fibonacci(n - 2);

}
//动态规划
int dp[100];
int Fibonacci2(int n) {
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];

}

int main()
{

	int n;
	while (cin >> n) {
		
		cout << Fibonacci2(n) << endl;

	}
}