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

package com.wyj.ch4;

/**
 * @author： wyj
 * @describe：
 * @version：V01
 * @date： 2021/7/28- 3:36
 */
public class h4a1b {
    /*
    f(1)=1  f(2)=2  f(3)=3  f(4)=4  f(5)=6
    f(n)=f(n-1)+f(n-3)  f(n-1)：前一年的牛 f(n-3)出生的牛
    暴力   时间复杂度O(2*N)
    * */
    public static int f1(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2|| n==3){
            return n;
        }
        return f1(n-1)+f1(n-3);

    }


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

        int res=3;      //f(i)    f(i-1)
        int pre=2;      //f(i-1)  f(i-2)
        int prepre=1;
        int tmp=0;
        int temp1=0;
        for (int i = 4; i <=n ; i++) {
            tmp=res;
            temp1=pre;
            res=res+prepre;//f(i)=f(i-1)+f(i-3)
            pre=tmp;//f(i-1)
            prepre=temp1;
        }
        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,0},{0,0,1},{1,0,0}};
        int[][]res=matrixPower(base,n-3);
//        return 3*res[0][0]+2*res[1][0]+res[2][0];
        return (3*res[0][0]+2*res[1][0]+res[2][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;
    }
}