可愛的小明特別喜歡爬樓梯柿究，他有的時候一次爬一個臺階，有的時候一次爬兩個臺階懦尝，有的時候一次爬三個臺階。如果這個樓梯有36個臺階壤圃，小明一共有多少種爬法呢陵霉？
這是典型的遞歸問題：小明爬到第36個臺階，可以從第35個臺階再爬1階上去伍绳；可以從第34個臺階再爬2階上去踊挠，也可以從第33個臺階再爬3階上去——所以，他爬36階可選擇的爬法的數(shù)目相當(dāng)于冲杀，爬35效床、34、33階可選擇的爬法的總數(shù)目权谁，而爬35剩檀、34、33階各自可選擇的爬法的數(shù)目旺芽，又可以像這樣計算沪猴，直到回到最簡單的爬3、2采章、1階可選擇的爬法的數(shù)目（依次是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;
}
它雖然很直觀，但速度卻比較慢抵怎。
于是再提供一份相對復(fù)雜翩活，但更快的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;
}