剑指Offer-08-跳台阶

题目

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

n<=39

解析

预备知识

此题为斐波那契数列的变形，也就是上一篇博客所讲的东西，只不过是数列的第0项为1，第1项为1，第二项为2。所以上一篇博客里面的代码只需改掉第0项的值为1，就可以完美解决这道题。我这里再重复说一下！

通项公式为：

f(n)=⎧⎩⎨1,1,f(n−1)+f(n−2),n == 0n == 1n > 1 f ( n ) = { 1 , n == 0 1 , n == 1 f ( n − 1 ) + f ( n − 2 ) , n > 1

思路一

就是按照通项公式写出递归形式即可。

/**
     * 普通递归
     * @param target
     * @return
     */
    public static int JumpFloor1(int target) {
        if(target ==  || target == ) {
            return ;
        }
        return JumpFloor1(target - ) + JumpFloor1(target - );
    }
           

思路二

上述递归存在一个问题，会重复计算相同子问题的解。

比如:

f(10) = f(9) + f(8)

f(9) = f(8) + f(7)

f(8) = f(7) + f(6)

f(7) = f(6) + f(5)

我们在计算f(10)的时候需要继续f(8)，而在f(9)也要再计算f(8),下面的计算也是，存在大量的重复的计算，复杂度只奔指数级别。这时我们可以把已计算过的子问题的结果记录下来，下次再碰到相同的子问题，直接取值即可。

static int[] steps = new int[];

    /**
     * 记忆化搜索
     * @param target
     * @return
     */
    public static int JumpFloor2(int target) {
        if(target ==  || target == ) {
            return ;
        }
        if(steps[target] != ) {
            return steps[target];
        }
        steps[target] = JumpFloor2(target - ) + JumpFloor2(target - );
        return steps[target];
    }
           

思路三

但记忆化搜索本身还是存在栈溢出的可能，递归的本质就是函数不断调用自身，即函数栈不断进行入栈操作，在递归深度达到一定程度时，必然会超过栈的内存限制，造成栈溢出。所以化递归为循环。

public static int JumpFloor3(int target) {
        if(target ==  || target == ) {
            return ;
        }
        int first = ;
        int second = ;
        int result = ;
        for(int i = ; i <= target; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }
           

思路四

利用矩阵快速幂来做，复杂度可以达到O(logn)。

矩阵快速幂的原理与普通数的快速幂一样，不清楚可以自行看看快速幂的原理，还是挺简单，利用指数二进制表示来分解乘法。减少了乘法次数。

我们发现f(n) = f(n - 1) + f(n - 2)。对应的矩阵形式为：

[f(n)f(n−1)]=[f(n)f(n−1)]∗[1110] [ f ( n ) f ( n − 1 ) ] = [ f ( n ) f ( n − 1 ) ] ∗ [ 1 1 1 0 ]

化简上式可得：

[f(n)f(n−1)]=[11]∗[1110]n−1 [ f ( n ) f ( n − 1 ) ] = [ 1 1 ] ∗ [ 1 1 1 0 ] n − 1

代码如下：

/**
     * 矩阵快速幂做法
     * @param n
     * @return
     */
    public static int JumpFloor4(int n) {
        if(n ==  || n == ) {
            return ;
        }
        int[][] base = {{, }, {, }};
        int[][] res = fastPowMatrix(base, n - );
        return res[][] + res[][];
    }

    /**
     * 矩阵快速幂
     * @param base
     * @param index
     * @return
     */
    public static int[][] fastPowMatrix(int[][] base, int index) {
        int[][] res = new int[base.length][base[].length];
        for(int i = ; i < base.length; i++) {
            res[i][i] = ;
        }
        int[][] t = base;
        while(index != ) {
            if((index & ) == ) {
                res = multipleMatix(res, t);
            }
            t = multipleMatix(t, t);
            index >>= ;
        }
        return res;
    }

    /**
     * 矩阵相乘
     * @param left
     * @param right
     * @return
     */
    public static int[][] multipleMatix(int[][] left, int[][] right) {
        int[][] res = new int[left.length][left[].length];
        for(int i = ; i < left.length; i++) {
            for(int j = ; j < right.length; j++) {
                for(int k = ; k < left[].length; k++) {
                    res[i][j] += left[i][k] * right[k][j];
                }
            }
        }
        return res;
    }
           

拓展

如果此题更改了跳台阶的条件，比如青蛙可以一次跳1次，跳2次,……跳n次，此时青蛙走到n阶台阶的总共有多少种呢？

请看下文！