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

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

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

给出一个整数 n，代表台阶数，一次可以跨 2 个或者 1 个台阶，请输出有多少种走法。

输入描述:

第一行一个整数 n。

输出描述:

输出走法数对 1e9 + 7 取模的值。

示例1

输入

输出

备注:

算法知识视频讲解

Java

pein531

这个数据范围，有点过分…有点过分啊。常规动态规划的O(N)算法完全不行，必须使用矩阵快速幂的算法，设斐波那契数列的第i项为f_i，对于某一项依赖前两项的二阶问题，都可以写成如下的通式：

$[f_{n},f_{n-1}]=[f_{n-1},f_{n - 2}]*\left[ \begin{matrix} a& b \\ c & d \\ \end{matrix} \right]$

对于斐波那契数列问题，可以根据前几项的初始值，可以解方程得到a=b=c=1，d=0。将等式右边的斐波那契矩阵递归替换直到初始值，可以得到

$[f_{n},f_{n-1}]=[f_{2},f_{1}]*\left[ \begin{matrix} 1& 1 \\ 1 & 0 \\ \end{matrix} \right]^{n-2}$

于是只要后面矩阵的次幂计算能够加速，就可以降低O(N)这个时间复杂度。这里可以利用矩阵的快速幂算法。首先考虑某个标量的快速幂：如10⁷⁵，75的二进制表示为(1001011)₂，记最终的结果为res=1，底数base=10，从最低位开始，最低位为1，将base乘进res，然后base平方；看倒数第二位为1，又将base乘进res，base继续平方；看倒数第三位为0（75不断右移并与1进行与运算可以知道最后一位是不是1），base不乘进res，但是它会继续平方……，周而复始直到遍历完75的最高位，算出的结果res就是我们要的答案。矩阵乘法同理，我们将标量的1对应为n阶单位矩阵，乘法用矩阵乘法就好。

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 <= 3){
            System.out.println(n);     // 小于等于3直接输出
        }else{
            long p = n - 1;
            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:36:11 回复(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((2 * res[0][1] + res[1][1]) % mod);
    }
}

发表于 2020-05-18 16:56:25 回复(0)