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

#include<iostream>
using namespace std;
//递归 
int fabonacci(int n){
	if(n==1||n==2)
		return n;
	return fabonacci(n-1)+fabonacci(n-2);
} 
//递归的优化，用数组记忆中间冗余计算的数据 
int f[101];
int fabonacci2(int n){
	if(f[n]!=-1)
		return f[n];
	else{
		if(n==1||n==2)
			return n;
		else{
			return fabonacci2(n-1)+fabonacci2(n-2);
		}
	}
}
//动态规划 
int dp[101];
int fabonacci3(int n){
	dp[1]=1;
	dp[2]=2;
	if(n==1||n==2){
		return n;
	}
	else{
		for(int i=3;i<101;i++)
			dp[i]=dp[i-1]+dp[i-2];
	}
	return dp[n];
}
int main()
{
	int n;
	for(int i=0;i<101;i++)
		f[i]=-1;
	while(scanf("%d",&n)!=EOF){
		printf("%d\n",fabonacci3(n));
	}
}