相信很多人第一次接触到台阶问题都是青蛙跳台阶吧，如下：
>>>一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）
可以推断出，
当台阶数是1时，只有一种跳法，当台阶数是2时，有两种跳法；
当台阶数是3时，第一次跳，要么是跳一级，要么是跳两级，这两种状态，产生两种完全不同的结果。
如果跳一级，那么剩下的就是n-1级台阶的跳法；
如果跳两级，那么剩下的就是n-2级台阶的跳法；
所以第一步怎么跳，决定了后续的跳法，所以总的跳法是f(n-1)+f(n-2)的跳法。
由此可以得出可以使用斐波那契数列求解：
//递归方法，数据较大时可能超时
int febonaci（int n）{ //n为台阶数 if(n==1) return 1; if(n==2) return 2; else return jumpFloor(n-2)+jumpFloor(n-1); }
//利用数组的循环方法
int febonaci(int n){
vector<int> v;
v.push_back(1); //先将数列前两个值放入
v.push_back(2);
for(int i=2;i<n;i++){
v.push_back(v[i-1]+v[i-2]); //数组内存储斐波那契数列
}
cout<<v[n-1]<<endl;
}
然后可以了解扩展题型：
>>>楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法
其实思想与前一题差不多，就当做熟悉题型了
第n阶=第n-1阶走一步总走法+第n-2阶走2步总走法+第n-3阶走3步总走法
int solve(int n){
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
for (int i = 3; i < n; i++){
v.push_back(v[i - 3] + v[i - 2] + v[i - 1]);
}
cout << v[n - 1] << endl;
}
//当然，为了约束运行时间，也可在读入数据前就构造好足够大的数列，然后直接进行输出
//这里同样给出递归算法，res为最终结果
long res;
void solve(int n)
{
if(n<0)
{
return;
}
if(n==0)
{
res++;
return;
}
for (int i=1; i<=3; i++)
{
solve(n-i);
}
}
int main（）{
……
cout<<solve(n)<<endl;
……
}
然后是台阶类问题的最终题型：
>>>有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式，一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod100003 （不通题目要求可能不同）后的结果
其实思想还是一样的，但是对于这种题目来说数据一般较大，不适用于递归写法，所以一般都是用数组解决
#include<iostream>
using namespace std;
int main()
{
int n,k;
vector<int> a(100003);
int i,j;
cin>>n>>k;//输入n、k
a[0]=1;//初始条件
for(i=1;i<=n;i++)//从头到尾进行递推
{
for(j=1; j<=k && i-j>=0 ;j++) //当前阶数最少1到最大k阶依次累加
a[i]+=a[i-j];
a[i]%=100003; //按要求进行处理
}
cout<<a[n]<<endl;
return 0;
}
以上~
