问题描述

一个台阶有n级，一次可以跳1级或者2级。问共有多少种跳法？分析算法的时间复杂度。

 

解决思路

假设f(n)代表n级台阶的跳法数目，其递推式如下：

当n=1时，f(n)=1;

当n=2时，f(n)=2;

其他，f(n)=f(n-1)+f(n-2)

 

那么有如下几种解决方法：

1. 递归，指数级时间复杂度；

2. 循环，O(n)时间复杂度，O(1)空间复杂度；

3. dp，O(n)时间复杂度，O(n)空间复杂度；

 

程序

见Fibonacci题：http://www.cnblogs.com/harrygogo/p/4623649.html