楼梯问题

hl给我的几道某公司的算法题：

1、

有个 100 级的楼梯，你可以每次跨 1级或2级，问跨到100级总共有多少种跨法。

 这个题目很容易写出递推式f(n) = f(n-1) + f(n-2),这个其实就是标准的斐波那契数列

使用自底向上的递推的动态规划算法来避免重复计算：

int fib(int n){

   int f0 = 1,f1 = 1;

   int i;

   for(i = 2; i < n; i++)

   	f2 = f0 + f1;

        f0 = f1;

	f1 = f2;

   }

   return f1;

}

 扩展一下也就是每次跨N1,N2,...Nk个台阶的跨法：

这个递推式：

f(n) = f(n-N1) + f(n-N2) + ... + f(n-Nk)

算法也很好写了，用一下从底往上推和记事本的动态规划方法代码分别如下：(待续)