递推实现动态规划

既然转移方程都给出了，直接根据转移方程从头到尾递递推一遍即可。

代码：

public class Solution {
    public int Fibonacci(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
  • 时间复杂度：
  • 空间复杂度：

递归实现动态规划

能以「递推」形式实现动态规划，自然也能以「递归」的形式实现。

为防止重复计算，我们需要加入「记忆化搜索」功能，同时利用某个值 在不同的样例之间可能会作为“中间结果”被重复计算，并且计算结果 固定，我们可以使用 static 修饰缓存器，以实现计算过的结果在所有测试样例***享。

代码：

public class Solution {
    static int N = 45;
    static int[] cache = new int[N];
    public int Fibonacci(int n) {
        if (n <= 1) return n;
        if (cache[n] != 0) return cache[n];
        cache[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return cache[n];
    }
}
  • 时间复杂度：
  • 空间复杂度：

打表

经过「解法二」，我们进一步发现，可以利用数据范围只有 进行打表预处理，然后直接返回。

代码：

public class Solution {
    static int N = 45;
    static int[] cache = new int[N];
    static {
        cache[1] = 1;
        for (int i = 2; i < N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
    }
    public int Fibonacci(int n) {
        return cache[n];
    }
}
  • 时间复杂度：将打表逻辑放到本地执行，复杂度为 ；否则为 ， 为常量，固定为
  • 空间复杂度：

矩阵快速幂

对于数列递推问题，可以使用矩阵快速幂进行加速，最完整的介绍在 这里 讲过。

对于本题，某个 依赖于 和 ，将其依赖的状态存成列向量：

目标值 所在矩阵为：

根据矩阵乘法，不难发现：

我们令：

起始时，我们只有 ，根据递推式得：

再根据矩阵乘法具有「结合律」，最终可得：

计算 可以套用「快速幂」进行求解。

代码：

class Solution {
    int[][] mul(int[][] a, int[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        int[][] ans = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < z; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return ans;
    }
    public int Fibonacci(int n) {
        if (n <= 1) return n;
        int[][] mat = new int[][]{
            {1, 1},
            {1, 0}
        };
        int[][] ans = new int[][]{
            {1},
            {0}
        };
        int x = n - 1;
        while (x != 0) {
            if ((x & 1) != 0) ans = mul(mat, ans);
            mat = mul(mat, mat);
            x >>= 1;
        }
        return ans[0][0];
    }
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「必考真题 の 精选」系列文章的第 No.65 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)