最经典的Fibonacci数，上楼梯每次能跨一步或者两步，问有多少中跨法；
对于最后一次跨一步或者两步，走到第 i 阶，其种类总数就是走到 i - 1 的总数 + 走到i - 2 的总数；于是 a [ i ] = a [ i - 1 ] + a [ i - 2 ]；当然，那个时候的我是用```组合数学做的```
1 #include<stdio.h> 2 long long c(int a,int b) 3 { 4 long long i,sum=1,j; 5 for (i=a,j=1;i>=a-b+1,j<=b;i--,j++) sum=sum*i/j; 6 return sum; 7 } 8 int main() 9 { 10 int N; 11 while (scanf("%d",&N)!=EOF) 12 { 13 int i; 14 for (i=0;i<N;i++) 15 { 16 long long M,j,sum=0; 17 scanf("%I64d",&M); 18 if (M!=1){ 19 M--; 20 for (j=0;j<=M/2;j++) sum+=c(j+M-j*2,j); 21 } 22 printf("%I64d\n",sum); 23 } 24 } 25 return 0; 26 }
hdu 2041（递推、dp/组合数学```其实就是Fibonacci数```）
原文：http://www.cnblogs.com/cenariusxz/p/4455067.html
