参考资料

动态规划入门

理解动态规划

左神 DP 思路

1.分析可变参数的范围，构造表格

2.标出计算的终止位置

3.标出不要计算直接出答案的位置 base case

4.推普遍位置如何依赖其他位置的

5.定出严格表依次计算的顺序

斐波那契数列

509. 斐波那契数

问题

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1 2	F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

动态规划

确定dp数组以及下标含义

dp[i]：第i个数的斐波那契数值为dp[i]

确定dp递推公式

$dp[i]=dp[i−1]+dp[i−2]$

初始化dp数组

1 2	dp[0] = 0; dp[1] = 1;

确定dp数组遍历顺序

根据 dp 公式， dp[i]是依赖 dp[i - 1]和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

举例推导dp数组

1	[0 1 1 2 3 5 8 13 21 34 55]

原始版本

public int fib(int N) {
    if (N <= 1) {
        return N;
    }
    // 定义dp数组
    int[] dp = new int[N + 1];
    // 初始化dp数组
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= N; ++i) {
        dp[i] = dp[i -1] + dp[i - 2];
    }
    // 返回计算终止位置
    return dp[N];
}

空间压缩版本

public int fib(int N) {
    if (N <= 1) {
        return N;
    }
    // 定义dp数组
    int[] dp = new int[2];
    // 初始化dp数组
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= N; ++i) {
        int sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    // 返回计算终止位置
    return dp[1];
}

矩阵快速幂

矩阵乘法

public int[][] muliMatrix(int[][] matrix1, int[][] matrix2) {
    int[][] ans = new int[matrix1.length][matrix2[0].length];
    for (int i = 0; i < matrix1.length; i++) {
        for (int j = 0; j < matrix2[0].length; j++) {
            for (int k = 0; k < matrix2.length; k++) {
                ans[i][j] += matrix1[i][k] * matrix2[k][j];
            }
        }
    }
    return ans;
}

矩阵快速幂

public int[][] matrixPower(int[][] matrix, int p) {
    int[][] ans = new int[matrix.length][matrix[0].length];
    // 先把ans设为单位矩阵
    for (int i = 0; i < ans.length; i++) {
        ans[i][i] = 1;
    }
    int[][] temp = matrix;
    while (p > 0) {
        // 二进制位中不为0的部分
        if ((p & 1) != 0) {
            ans = muliMatrix(ans, temp);
        }
        p >>= 1;
        temp = muliMatrix(temp, temp);
    }
    return ans;
}

fib

public int fib(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    int[][] base = {{1, 1}, {1, 0}};
    int[][] res = matrixPower(base, n - 2);
    return res[0][0] + res[1][0];
}