题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
分析与代码
走n阶楼梯，无论是走一次走1阶还是2阶，总得迈出一步，
所以求n阶楼梯的走法数F(n)，可以看成是走F(n-1)和F(n-2)
的和。
而当楼梯只剩1阶时，就只有1种走法了；
剩2阶时，可以选择1阶阶走，也可以直接走2阶，
所以是2种走法；
以此得出边界条件：n1 和 n2，可以很愉快的写出以下递归代码
#include<iostream>
using namespace std;
int F(int n){
if(n==1)return 1;
if(n==2)return 2;
return F(n-1)+F(n-2);
}
int main(){
int n;
cin>>n;
cout<<F(n)<<endl;
return 0;
}
很明显，简单递归会出现很多重复计算。
如：F(n-2)会被F(n-1-1)计算一次，被F(n-2)计算一次。
而回观上面我们写的函数返回表达式很容易让我们联想到
斐波那契的递推式，由此可以得出DP的状态转移方程：
F(1)=1 , F(2)=2 , F(n)=F(n-1)+F(n-2)
其中n≥3。
#include<iostream>
using namespace std;
const int N=100010;
int F[N];
int main(){
int n;
cin>>n;
F[1]=1;
F[2]=2;
for(int i=3;i<n;i++)F[i]=F[i-1]+F[i-2];
return 0;
}
到这里你以为完了吗？不！并没有！！！
(如果你是有用Java和Python这种不太需要考虑数据范围的当我没说)
本人亲测，int的话n到1500就炸了，long long到2000也不行...
所以这题要AC还得用高精度！！！
(未完待续......)
