斐波那契数列

Question

问题

• 给定整数 N ，一次可以跨 1 个台阶或者 2 个台阶，请问一共有多少种走法（要求使用对数级别的时间复杂度）

解答

• 常规思路（ F(n) = F(n-1)+F(n-2) ）
• 增加一个数组进行存储，动态规划，可以完成 O(n) 的时间复杂度
• 矩阵计算：就像对 a 的 b 次方的对数级方案
  • 对于为什么 2*result[0][0]+result[1][0] ，可以进一步考虑 N = 3 的场景
  • base 数组根据前 4 个值即可算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String mn = scanner.nextLine();
        Integer N = Integer.valueOf(mn);
        int[][] base = {{1,1},{1,0}};
        int[][] result = matrixPower(base,N-2);
        System.out.println(2*result[0][0]+result[1][0]);
        System.out.println(checkResult(N));
    }

    private static int checkResult(Integer n) {
        if (n == 1 || n == 2){
            return n;
        }
        if (n <= 0) return 0;
        return checkResult(n-1) + checkResult(n-2);
    }

    public static int[][] matrixPower(int [][] m, int p){
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0;i < res.length;i ++) {
            res[i][i] = 1;
        }
        int[][] temp = m;
        for (;p != 0;p >>= 1){
            if ((p & 1) != 0){
                res = matrixPower(res,temp);
            }
            temp = matrixPower(temp,temp);
        }
        return res;
    }

    public static int[][] matrixPower(int [][] m1, int[][] m2) {
        int [][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m2[0].length; i ++){
            for (int j = 0; j < m1.length; j ++){
                for (int k = 0; k < m2.length; k ++){
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
}