[算法专栏] 爬楼梯问题

  一个台阶总共有n 级,如果一次可以跳1 级,也可以跳2 级,求总共有多少种跳法。

  备注:

  这个题目经常出现,包括Microsoft 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。

  问题分析:

  如果只有1 级台阶,那显然只有一种跳法;

  如果有2 级台阶,那就有两种跳的方法了:一种是分两次跳,每次跳1 级;另外一种就是一次跳2 级。

  当台阶数>2 级时,第一次跳的时候就有两种不同的选择:一种是 第一次只跳1 级,此时跳法数目等于后面剩下的n-1 级台阶的跳法数目,即为f(n-1);另外一种选择是第一次跳2 级,此时跳法数目等于后面剩下的n-2 级台阶的跳法数目,即为f(n-2)。 所以,n 级台阶时的不同跳法的总数 f(n) = f(n-1) + f(n-2)。

           /  1       (n=1)
  即:f(n) =  2         (n=2)
           \  f(n-1) + (f-2)   (n>2)

  其实,这就是Fibonacci 序列。算法复杂度为:(O(n))。 

  伪代码如下:

int Fibonacci1(unsigned int N) { if(N<=2) return N; int fibtwo=2; int fibone=1; int fibN=0; for(unsigned int i=3;i<=N;i++) { fibN=fibone+fibtwo; fibone=fibtwo; fibtwo=fibN; } return fibN; }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwspsj.html