跳台阶问题 【微软面试100题 第二十七题】

题目要求:

  一个台阶总共有n阶,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法,并分析算法的时间复杂度。

题目分析:

  f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2;--->f(3)=f(2)+f(1)=2+1;------>f(3)=Fibonacci(4)=Fibonacci(3)+Fibonacci(2) = 2+1;即问题转换为斐波那契数列的n+1项。

  参考链接:http://www.cnblogs.com/tractorman/p/4058305.html

  可使用参考链接中的公式法,时间复杂度为O(n).

原文地址:https://www.cnblogs.com/tractorman/p/4059661.html