题解 | #跳台阶#

跳台阶

http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

题意整理

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

方法一（迭代）

1.解题思路

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

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

图解展示： alt

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 - 2$ 次，所以时间复杂度为 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O (1)$ 。

方法二（矩阵快幂法）

1.解题思路

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

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

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

本题中 $f (0) = 1$ ， $f (- 1) = 0$ ，所以 $f (n)$ 刚好等于 $\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right]^{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;
    }
}