“小明爬楼梯”问题

问题来源

可爱的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶，有的时候一次爬三个台阶。如果这个楼梯有36个台阶，小明一共有多少种爬法呢？

这是典型的递归问题：小明爬到第36个台阶，可以从第35个台阶再爬1阶上去；可以从第34个台阶再爬2阶上去，也可以从第33个台阶再爬3阶上去——所以，他爬36阶可选择的爬法的数目相当于，爬35、34、33阶可选择的爬法的总数目，而爬35、34、33阶各自可选择的爬法的数目，又可以像这样计算，直到回到最简单的爬3、2、1阶可选择的爬法的数目（依次是4种、2种和1种）。

于是我们得到答案：小明这样爬36个台阶，一共有2082876103种爬法。

下面是解决该问题的一份C程序代码：

#include<stdio.h>
int f(int n){
    switch(n){
        case 1:
            return 1;
        case 2:
            return 2;
        case 3:
            return 4;
        default:
            return f(n-1)+f(n-2)+f(n-3);
    }
}
int main(){
    printf("%d\n",f(36));
    return 0;
}

它虽然很直观，但速度却比较慢。

于是再提供一份相对复杂，但更快的C程序代码：

#include<stdio.h>
long f(int n){
    n++;
    int i;
    long table[n];
    for(i=0;i<n;i++){
        table[i]=0;
    }
    table[1]=1;
    table[2]=2;
    table[3]=4;
    for(i=4;i<n;i++){
        table[i]=table[i-1]+table[i-2]+table[i-3];
    }
    return table[n-1];
}
int main(){
    printf("%d\n",f(36));
    return 0;
}