题意整理

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

方法一（迭代）

1.解题思路

本题是一个基本的递归问题，假设跳上n级台阶有$f(n)f(n)$中跳法，则跳上n-1级、n-2级分别有$f(n-1)f(n-1)$、$f(n-2)f(n-2)$种跳法。青蛙既可以从n-1级台阶跳到n级，也可以从n-2级台阶跳到n级，所以有$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$。使用递归很容易实现，但是当n很大时，递归栈的深度也会很大，可能报栈深度溢出的错误。并且中间会有很多重复的计算。可以使用两个变量分别记录前一阶以及前两阶台阶时的情况，避免上述情况。

• 定义a、b两个变量，a记录前两阶的跳法，b记录前一阶的跳法。
• 从3开始遍历每一阶的情况，利用$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$计算当前台阶的总跳法，同时跟新a、b。

图解展示：

2.代码实现

public class Solution {
    public int jumpFloor(int target) {
        //特殊情况处理
        if(target==1||target==2){
            return target;
        }
        //a记录前两阶的跳法，b记录前一阶的跳法
        int a=1;
        int b=2;
        //sum记录当前台阶的跳法
        int sum=0;
        for(int i=3;i<=target;i++){
            //f(i)=f(i-2)+f(i-1)，既可以从前两个台阶处跳到当前，也可以从前一个台阶处跳到当前
            sum=a+b;
            //更新a、b
            a=b;
            b=sum;
        }
        return sum;

    }
}

3.复杂度分析

• 时间复杂度：假设目标台阶数为n，需要循环$n-2n-2$次，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。

方法二（矩阵快幂法）

1.解题思路

从方法一，我们知道有$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$，把它转化为矩阵乘法的形式，则有：$\left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(n)\; \backslash \backslash \; f(n-1)\; \backslash end\{matrix\}\; \backslash right]$=*$\left[\begin{array}{c}f(n-1)\\ f(n-2)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(n-1)\; \backslash \backslash \; f(n-2)\; \backslash end\{matrix\}\; \backslash right]$，

从而我们知道前一项$\left[\begin{array}{c}f(n-1)\\ f(n-2)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(n-1)\; \backslash \backslash \; f(n-2)\; \backslash end\{matrix\}\; \backslash right]$=*$\left[\begin{array}{c}f(n-2)\\ f(n-3)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(n-2)\; \backslash \backslash \; f(n-3)\; \backslash end\{matrix\}\; \backslash right]$，

于是有：$\left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(n)\; \backslash \backslash \; f(n-1)\; \backslash end\{matrix\}\; \backslash right]$=*$\left[\begin{array}{c}f(0)\\ f(-1)\end{array}\right]\backslash left[\; \backslash begin\{matrix\}\; f(0)\; \backslash \backslash \; f(-1)\; \backslash end\{matrix\}\; \backslash right]$

本题中$f(0)=1f(0)=1$，$f(-1)=0f(-1)=0$，所以$f(n)f(n)$刚好等于的第0行第0列。

2.代码实现

public class Solution {
    public int jumpFloor(int target) {
        //特殊情况处理
        if(target==1||target==2){
            return target;
        }
        int[][] a=new int[][]{{1,1},{1,0}};
        
        return fastpow(a,target)[0][0];

    }
    
    //矩阵快幂法计算a的k次幂
    private int[][] fastpow(int[][] a,int k){
        //基数矩阵
        int[][] res=new int[][]{{1,0},{0,1}};
        while(k!=0){
            //k为奇数时，res需要乘以a
            if(k%2==1){
                res=multiply(res,a);
            }
            //k减半，a翻倍
            k/=2;
            a=multiply(a,a);
        }
        return res;
    }
    
    //自定义2*2矩阵乘法
    private int[][] multiply(int[][] a,int[][] b){
        int[][] res=new int[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                res[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：假设目标台阶数为n，fastpow最多执行$lo{g}_{2}nlog\_2n$次，所以时间复杂度为$O(lo{g}_{2}n)O(log\_2n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。