1.问题描述

一个人爬楼梯，每次只能爬1个或两个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法

2.分析

如果n==1，显然只有从0->1一种方法f(1)=1；
如果n==2，那么有0->1->2、0->2两种方法f(2)=2;
如果n==3,那么可以先爬到第1阶，然后爬两个台阶，或者先爬到第二阶，然后爬一个台阶，显然f(3)=f(2)+f(1);
……
推广到一般情况，对于n(n>=3)个台阶,可以先爬到第n-1个台阶，然后再爬一个台阶，或者先爬到n-2个台阶，然后爬2个台阶，因此有f(n)=f(n-1)+f(n-2)。
那么动态规划的递推公式和边界条件都有了，即：

3.程序代码

根据递推公式，可以写如下代码轻松解决问题:

#include<stdio.h>
long long fun(int n);
int main()
{
    printf("%lld ",fun(80));
    return 0;
}
long long fun(int n)
{
    if(n==1)
        return 1;
    else if(n==2)
        return 2;
    else if(n>2)
        return fun(n-1)+fun(n-2);
}

注意：fun（80）的结果非常大，程序运行时间很长，测试的时候可以用小一点的数字测试。
虽然代码简单，但是显然这种方法实在是太耗时间了，递归函数多次重复计算中间结果。我们改进以下，开一个数组来保存中间结果。

#include<stdio.h>
long long calc(long long step[],int n);
long long step[101]={0};
int main()
{
    int n;
    scanf("%d",&n);
    int i=1;
    for(i=1;i<=n;i++)
        printf("%lld ",calc(step,i));

    return 0;
}
long long calc(long long step[],int n)
{
    long long i;
    if(n<=0)
        return 0;
    step[0]=1;
    step[1]=1;
    if(n>=2&&step[n-1]>0&&step[n-2]>0)
    {
        step[n] = step[n-1] + step[n-2];
        return step[n];
    }
    else if(n>=2)
    {
        for(i=2;i<=n;i++)
            step[i] = step[i-1]+step[i-2];
    }
    return step[n];
}