剑指offer - 跳台阶(Java实现)

题目链接：https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&&tqId=11161&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  此题目与斐波那契数列相同，但是需要注意 F[0] 与 F[1] 的取值。我们用dp的思想来思考这个问题，dp[i] 表示当前阶梯一共有多少种跳法。我们可以从 i - 1 层阶梯跳一步到达第 i 层，也可以从 i - 2 层阶梯跳两步到达第 i 层，那么到达第 i 层的跳法就是到达 i - 1 层和 i - 2 层，dp[i] = dp[i - 1] + dp[i - 2]。由题意知道 dp[1] = 1, dp[2] = 2。

斐波那契数列：https://blog.nowcoder.net/n/cd299d5800474998938aedac8d7f6515
  方法一：递推

public class Solution {
    static int[] fib = new int[100];
    public int JumpFloor(int target) {
        fib[0] = 1; fib[1] = 1;
        for(int i = 2; i <= target; ++ i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[target];
    }
}

  方法二：矩阵快速幂

public class Solution {
    public int JumpFloor(int target) {
        if(target == 0) return 1;
        if(target == 1) return 1;
        int[][] ans = new int[2][2];
        init(ans);
        ans = quickPow(ans, target - 1);
        return ans[0][0] + ans[0][1];
    }

    public static void init(int[][] ans) {
        ans[0][0] = 1; ans[0][1] = 1;
        ans[1][0] = 1; ans[1][1] = 0;
    }

    public static int[][] quickPow(int[][] res, int b) {
        int[][] ans = new int[2][2];
        ans[0][0] = 1; ans[0][1] = 0; ans[1][0] = 0; ans[1][1] = 1;
        while(b > 0) {
            if(b % 2 == 1) ans = mul(ans, res);
            res = mul(res, res);
            b >>= 1;
        }
        return ans;
    }
    public static int[][] mul(int[][] a, int[][] b) {
        int[][] z = new int[2][2];
        for(int i = 0; i < 2; ++ i) {
            for(int j = 0; j < 2; ++ j) {
                z[i][j] = 0;
                for(int k = 0; k < 2; ++ k) {
                    z[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return z;
    }
}