题目主要信息

1、一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

2、要求：时间复杂度：$O(n)O(n)$，空间复杂度： $O(1)O(1)$

方法一：菲波那切数列方法

具体方法

自顶向下的方法，比如求f(6)，可以转化为求f(4)+f(5),在依次向下求解，如下图所示。

Java代码

public class Solution {
    public int jumpFloor(int target) {
        if(target<=1){
            return 1;
        }
        return jumpFloor(target-1)+jumpFloor(target-2);
    }
}

复杂度分析

时间复杂度：$O((\mathrm{（}1+\sqrt{5}\mathrm{）}\mathrm{/}2{)}^n)O((（1+\backslash sqrt\{5\}）/2)^n)$求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2). F(n)= F(n-1)+F(n-2) 我们把计算F(i)所需要的时间记为T(i)。然后记计算加法所需的时间为1，那么显然有 T(n) = 1+ T(n-1)+T(n-2)

这一式子可以进行变形，两边同时加1，得到

T(n)+1 = (T(n-1)+1)+(T(n-2)+1)

记T(n)+1=A(n),那么显然

A(n)=A(n-1)+A(n-2)

这是一个斐波那契数列，只不过初项有所不同。

但是斐波那契数列的增长率与初项无关。证明如下：

设某斐波那契数列的前两项为a,b,令c=max(a,b),显然这个数列的增长速度不会超过以c为初项的斐波那契数列。

那么显然，以c为初项的斐波那契数列，它的元素是

空间复杂度：$O(n)O(n)$，递归调用的栈深度

方法二：迭代

具体方法

可以推导一下公式

f(0) = 1

f(1) = 1

f(2) = 2

f(3) = 3

f(4) = 5 = f(2)+f(3)

f(5) = 8 = f(3)+f(4)

...

f(n) = f(n-1)+f(n-2)

Java代码

public class Solution {
    public int jumpFloor(int target) {
        int a = 1, b = 1;
        int sum = 0;
        if(target == 0) return a;
        if(target ==1) return b;
        for(int i=2;i<=target;i++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历到target即可
• 空间复杂度：$O(1)O(1)$，一个临时变量存结果