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

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

文章目录

• 一、问题描述
• 二、分析
• 三、代码
• 四、结果

一、问题描述

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

二、分析

如果只有1 级台阶，那显然只有一种跳法；
如果有2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1 级；另外一种就是一次跳2 级。

一般情况：把n 级台阶时的跳法看成是n 的函数，记为f(n)。
当n>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)

三、代码

四、结果

—— 2018-11-29 ——