题解 | #斐波那契数列问题的递归和动态规划2#

package com.wyj.ch4;

/**
 * @author： wyj
 * @describe：
 * @version：V01
 * @date： 2021/7/28- 3:31
 */
public class h4a1a {
    /*给出一个整数 n，代表台阶数，一次可以跨 2 个或者 1 个台阶，请输出有多少种走法。
    f(1)=1  f(2)=2  f(n)=f(n-1)+f(n-2)
    暴力   时间复杂度O(2*N)
    * */
    public static int f1(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return n;
        }
        return f1(n-1)+f1(n-2);

    }

    /*f2:从左到右依次求出每一项的值，通过顺序计算求到第N项
    时间复杂度O(N)
    * */
    public static int f2(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return n;
        }

        int res=2;//f(i)    f(i-1)
        int pre=1;//f(i-1)  f(i-2)
        int tmp=0;
        for (int i = 3; i <=n ; i++) {
            tmp=res;
            res=res+pre;//f(i)=f(i-1)+f(i-2)
            pre=tmp;//f(i-1)
        }
        return res;

    }


    /*矩阵乘法
    时间复杂度：O(logN)
    int mod=(int) (1e9+7);
    为防止数越界，最后输出第n项对mod取模的值
    * */
    public static int f3(int n){
        int mod=(int) (1e9+7);
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return n;
        }
        int[][]base={{1,1},{1,0}};
        int[][]res=matrixPower(base,n-2);
//        return 2*res[0][0]+res[1][0];
        return (2*res[0][0]+res[1][0])%mod;

    }

    //求矩阵m的p次方
    public static int[][] matrixPower(int [][]m,int p){
        int[][]res=new int[m.length][m[0].length];
        //先把res设为单位矩阵，相当于整数中1
        for (int i = 0; i < m.length; i++) {
            res[i][i]=1;
        }

        int[][]tmp=m;
        //求p对应的二进制
        for(;p!=0;p>>=1){
            if((p&1)!=0){
                res=mulMatrix(res,tmp);
            }
            tmp=mulMatrix(tmp,tmp);
        }

        return res;
    }

    //矩阵m1 矩阵m2相乘
    public static int[][] mulMatrix(int [][]m1,int [][]m2){
        int mod=(int) (1e9+7);
        int[][] res=new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
//                    res[i][j]=res[i][j]+m1[i][k]*m2[k][j];
                    res[i][j]=(res[i][j] + (m1[i][k]*m2[k][j])%mod)%mod;
                }
            }
        }

        return res;
    }



}