N阶楼梯上楼问题

题目描述

N阶楼梯上楼问题，一次可以走两阶或者一阶，问又多少种上楼方式

分析

典型的动态规划问题，N阶楼梯可以由N-1阶上来，也可以由N-2阶上来
F[N] = F[N-1]+F[N-2]

代码

#include<iostream>
using namespace std;

const int MaxN=91;
int F[MaxN];//F[i]保存上i阶楼梯时的方案数

int main()
{
    int N;
    while(cin>>N)
    {
        F[1]=1;
        F[2]=2;
        for(int i=3;i<=N;i++)
        {
            F[i]=F[i-1]+F[i-2];
        }
        cout<<F[N]<<endl;
    }
    return 0;
}