青蛙跳台阶，能写一个复杂度更低的解法吗？

大家好，我是年年！今天的内容是关于一道算法题——青蛙跳台阶。这是一个面试很喜欢考的题，看到它，大部分人脑海中应该立马出现：斐波那契亚数列——递归——f(n)=f(n-1) f(n-2)。

但辅导的小伙伴上周在面试中遇到的问题是：除了递归，能不能写出别的解法，降低算法的时间复杂度。这篇文章给出这道题的更优解。

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

分析

这是一个最基础的动态规划类问题，首先来讲一下思路：当n较小时，可以直接枚举得到结果：

n=1时，青蛙仅有直接跳上一级台阶这种跳法，即一种跳法;n=2时，青蛙可以先跳 上 1 级，然后再跳 上 1 级到达2级台阶，；也可以直接跳 2 级台阶，即一共有两种解法;

当n较大时，去枚举不现实了。但可以想象一下青蛙“最后一跳”有哪些情况：因为青蛙一次可以跳1个或2个台阶，所以只可能是两种情况：从n-1级跳1级上去，以及从n-2阶的位置跳2级上去。我们想要知道跳n级台阶有多少种解法，只需要知道跳n-1级台阶和跳n-2级台阶的跳法，把他们加起来就可以。即得到一个公式f(n)=f(n-1) f(n-2)。

常规解法(递归)

看到这个式子f(n)=f(n-1) f(n-2)，应该很快能反应：斐波那契亚数列，代码很容易写出来。递归的关键是确认递归出口，即：当只有1级台阶，只有一种跳法；只有2级台阶时，有两种跳法。

代码如下：

function frogJump(n) {

if (n