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

[编程题]斐波那契数列问题的递归和动态规划

热度指数：6677 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个整数 n，请输出斐波那契数列的第 n 项对 1e9 + 7 取模的值。

输入描述:

第一行一个整数 n。

输出描述:

输出第 n 项对于 1e9 + 7 取模的值。

示例1

输入

输出

备注:

算法知识视频讲解

Java

pein531

矩阵的快速幂求解，让直接线性动态规划的O(N)时间复杂度降低为O(logN)。能这么做的条件是：除了初始的几项，dp序列中某一项的计算必须严格依赖前面的某几项，无论递归深度达到多少都满足，不存在终止递归的递归头，程序什么时候停止完全依赖于你设置让它算到哪一轮。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long[][] base = {{1, 1}, {1, 0}};
        long[][] res = {{1, 0}, {0, 1}};     // 单位矩阵
        if(n <= 2){
            System.out.println(1);     // 小于等于2直接输出
        }else{
            long p = n - 2;
            for(; p != 0; p >>= 1){
                if((p & 1) != 0) res = multiMat2D(res, base);
                base = multiMat2D(base, base);
            }
            System.out.println((res[0][0] + res[1][0]) % MOD);
        }
    }
    
    private static long[][] multiMat2D(long[][] A, long[][] B) {
        return new long[][]{{(A[0][0] * B[0][0] % MOD) + (A[0][1] * B[1][0] % MOD), (A[0][0] * B[0][1] % MOD) + (A[0][1] * B[1][1] % MOD)}, 
                            {(A[1][0] * B[0][0] % MOD) + (A[1][1] * B[1][0] % MOD), (A[1][0] * B[0][1] % MOD) + (A[1][1] * B[1][1] % MOD)}};
    }
}

发表于 2021-11-25 10:42:32 回复(0)

Java

momonn

本题的输入非常大，需要将左神的代码转为大数类型

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    static long n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        BigInteger res = f(n);
        System.out.println(res);
    }

    private static BigInteger f(long n) {
        if (n <= 2) return BigInteger.ONE;
        BigInteger[][] base = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};
        BigInteger[][] res = matrixPower(base, n - 2);
        return (res[0][0].add(res[1][0])).mod(new BigInteger(String.valueOf(mod)));
    }

    private static BigInteger[][] matrixPower(BigInteger[][] m, long p) {
        BigInteger[][] res = new BigInteger[m.length][m[0].length];
        //初始化res
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                if (i == j) {
                    res[i][j] = BigInteger.ONE;
                } else {
                    res[i][j] = BigInteger.ZERO;
                }
            }
        }
        BigInteger[][] tmp = m;
        while (p > 0) {
            if ((p & 1) == 1) res = muliMatrix(res, tmp);
            tmp = muliMatrix(tmp, tmp);
            p >>= 1;
        }
        return res;
    }

    private static BigInteger[][] muliMatrix(BigInteger[][] m1, BigInteger[][] m2) {
        BigInteger[][] res = new BigInteger[m1.length][m2[0].length];
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                res[i][j] = BigInteger.ZERO;
            }
        }
        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].add(m1[i][k].multiply(m2[k][j]))).mod(new BigInteger(String.valueOf(mod)));
                }
            }
        }
        return res;
    }
}

发表于 2020-07-04 16:37:19 回复(0)

Java

jahentao

求出二阶递推数列 $二阶递推数列$ 的状态矩阵 $状态矩阵$ 。

$推导$

用矩阵快速幂求解矩阵幂。

注意到N的范围 $图片说明$ ，用8个字节整数表示。

import java.util.*;
public class Main {
    public static final int mod = 1_000_000_007;
    public static long[][] multiply(long[][] matrix1, long[][] matrix2) {
        long[][] res = new long[matrix1.length][matrix1.length];
        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                long sum = 0;
                for (int k = 0; k < matrix1.length; k++)
                    sum = (sum + (matrix1[i][k] * matrix2[k][j]) % mod) % mod;
                res[i][j] = sum;
            }
        }
        return res;
    }
    public static long[][] powerN(long N, long[][] matrix) {
        long[][] res = new long[matrix.length][matrix.length];
        for (int i = 0; i < res.length; i++) 
            res[i][i] = 1;
        while (N != 0) {
            if ((N & 1) == 1) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            N = N >>> 1;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        sc.close();
        if (N < 1) {
            System.out.println(0);
            return;
        }
        if (N == 1) {
            System.out.println(1);
            return;
        }
        long[][] matrix = {{1, 1}, {1, 0}};
        long[][] res = powerN(N - 1, matrix);
        System.out.println((res[1][0] + res[1][1]) % mod);
    }
}

发表于 2020-05-18 16:32:50 回复(0)

Java