LeetCode1137.第N个泰波那契数列：「状态DP」&「矩阵快速幂」

浏览次数 : 次 2022-01-17

博文字数统计 : 1.8k字 | 阅读所需时长 : 8分

× 文章目录

1. LeetCode1137.第N个泰波那契数列：「状态DP」&「矩阵快速幂」
2. \end{gathered}

LeetCode1137：第N个泰波那契数列
- 时间：2022-01-17
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组
- 算法：状态机、动态规划、矩阵快速幂、递归

LeetCode1137.第N个泰波那契数列：「状态DP」&「矩阵快速幂」

1. 题目描述

题目：原题链接
- 给你一个整数 n，返回泰波那契数列的第 n 个数字
- 泰波那契数列：$T_0 = 0$, $T_1 = 1$，$T_2 = 1$，$T_{n+3} = T_n +T_{n+1}+T_{n+2}$
- 0 <= n <= 37
输入输出规范：
- 输入：整数 n
- 输出：第 n 个泰波那契数
输入输出示例
- 输入：n = 25
- 输出：1389537

2. 方法一：递归 & 记忆化

思路
- 本题存在很明显的递推关系，最简单的思路就是直接根据公式递归，递归的终止条件也非常明显，就是 n <= 2 的时候
- 但是递归会不断的调用方法，n 特别大的时候，一方面时间复杂度较高，另一方面方法会占用大量栈空间，在空间上面也有隐患
- 实际上，递归的过程中，会出现大量的重复计算，可以通过记忆化的方式来进行优化，避免重复计算

题解：直接递归，n = 35时超时

public int tribonacci(int n) {
       if(n <= 1) return n;
       if(n == 2) return 1;
       return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
   }

题解：递归 & 记忆化

private int[] memo = new int[38];
public int tribonacci(int n) {
    if(n <= 1) return n;
    if(n == 2) return 1;
    if(memo[n] != 0) return memo[n];
    memo[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
    return memo[n];
}

复杂度分析(优化后)：n 是输入的整数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

3. 方法二：动态规划

思路
- 对于这种具有递推关系的题目，动态规划同样是一种常规方法，相当于将递归转换为迭代的方式
- 对于本题，因为当前状态只和其前面三个状态相关，所以可以将DP数组优化为三个普通的变量，降低空间复杂度

题解：直接DP

public int tribonacci(int n) {
    if(n <= 1) return n;
    if(n == 2) return 1;
    int[] dp = new int[n+1];
       dp[0] = 0;
       dp[1] = 1;
       dp[2] = 1;
       for(int i = 3; i < n+1; i++) {
           dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
       }
       return dp[n];
   }

题解：空间优化

public int tribonacci(int n) {
    if(n <= 1) return n;
    if(n == 2) return 1;
    int a = 0, b = 1, c = 1;
    int res = 0;
    for(int i = 3; i < n+1; i++) {
        res = a + b + c;
        a = b;
        b = c;
        c = res;
    }
    return res;
}

复杂度分析(优化后)：n 是输入的整数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

4. 方法三：矩阵快速幂

思路：矩阵乘法 & 快速幂
- 对于状态机DP问题而言，如果状态转移的过程可以表示为线性的叠加，就可以转换为矩阵计算来提高效率
- 为了求出dp[n]，状态DP一般都需要遍历次，即线性的时间复杂度 $O(n)$，而矩阵计算可以通过矩阵具有结合律的性质来将复杂度优化到对数级 $O(logn)$
- 这种方法可以正确求解结果的根本原因是矩阵乘法，具体推导涉及到线性代数的知识，而复杂度为对数级是因为在求解矩阵时使用了快速幂算法
快速幂
- 快速幂是用于求解 x 的 n 次幂问题的一种算法，通过奇偶次幂的判断并分类讨论，将线性复杂度二分为对数复杂度
- 具体而言，是在偶次幂时进行矩阵平方并将幂除2，奇次幂时进行矩阵与初始值相乘并赋值给初始值
矩阵乘法
- 矩阵乘法要求前一个矩阵的列数等于后一个矩阵的行数
- 相乘得到的矩阵的行数与前一个矩阵行数相等，列数与后一个矩阵列数相等
状态机DP转化为矩阵乘法的过程，以本题为例
- 对于本题，根据递推公式 $T_{n+3} = T_n +T_{n+1}+T_{n+2}$ 以及矩阵乘法的性质，可以得到
  $$
  \begin{gathered}
  \begin{bmatrix}
  T(i)
  \ T(i - 1)
  \ T(i - 2)
  \end{bmatrix}
  
  \end{gathered}
  \begin{gathered}
  \begin{bmatrix}
  T(i - 1)1+T(i - 2)1+T(i - 3)1 \
  T(i - 1)1+T(i - 2)0+T(i - 3)0 \
  T(i - 1)0+T(i - 2)1+T(i - 3)*0
  \end{bmatrix}
  \end{gathered}=
  
  \begin{gathered}
  \begin{bmatrix}
  1 & 1 & 1 \
  1 & 0 & 0 \
  0 & 1 & 0
  \end{bmatrix}*
  \end{gathered}
  \begin{gathered}
  \begin{bmatrix}
  T(i - 1)
  \ T(i - 2)
  \ T(i - 3)
  \end{bmatrix}
  \end{gathered}
  $$
- 其中，我们可以得到一个状态转移的系数矩阵 M：
  $$
  M=\begin{gathered}
  \begin{bmatrix}
  1 & 1 & 1 \
  1 & 0 & 0 \
  0 & 1 & 0
  \end{bmatrix}
  \end{gathered}
  $$
- 将矩阵形式递推到 $T(n)$，根据矩阵的结合律，可以得到：
$$
\begin{gathered}
\begin{bmatrix}
T(n)
\ T(n - 1)
\ T(n - 2)
\end{bmatrix}
\end{gathered}
= M*
\begin{gathered}
\begin{bmatrix}
T(n - 1)
\ T(n - 2)
\ T(n - 3)
\end{bmatrix}
\end{gathered}=
M^{n-2}*
\begin{gathered}
\begin{bmatrix}
T(0)
\ T(1)
\ T(2)
\end{bmatrix}
\end{gathered}=M^{n-2}*
\begin{gathered}
\begin{bmatrix}
1
\ 1
\ 0
\end{bmatrix}
\end{gathered}
$$
- 所以就将整个过程化简为求矩阵 M 的 n-2 次幂问题，实际上就是矩阵乘法，结合快速幂算法，求出矩阵 M 后，与初始状态做矩阵乘法，得到的结果矩阵的第一个元素就是我们要求的结果

题解：初始数组使用初始值填充，一维

public int tribonacci(int n) {
    if (n <= 1) return n;
    if (n == 2) return 1;
    int[][] ini = new int[][]{
        {1},{1},{0}
    };
    int[][] matrix = new int[][]{
        {1, 1, 1},
        {1, 0, 0},
        {0, 1, 0}
    };
    int x = n - 2;
    while (x > 0) {
        if ((x & 1) == 1) {
            ini = mul(matrix, ini);
        }
        matrix = mul(matrix, matrix);
        x >>= 1;
    }
    //        for (int[] ints : ini) {
    //            System.out.println(Arrays.toString(ints));
    //        }
    return ini[0][0];
}

private int[][] mul(int[][] matrixA, int[][] matrixB) {
    int row = matrixA.length;
    int col = matrixB[0].length;
    int[][] res = new int[row][col];
    int size = matrixB.length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            for (int k = 0; k < size; k++) {
                res[i][j] += matrixA[i][k] * matrixB[k][j];
            }
        }
    }
    return res;
}

题解：初始值使用对角矩阵填充，二维

public int tribonacci(int n) {
    if (n <= 1) return n;
    if (n == 2) return 1;
    int[][] ini = new int[][]{
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1}
    };
    int[][] matrix = new int[][]{
        {1, 1, 1},
        {1, 0, 0},
        {0, 1, 0}
    };
    int x = n - 2;
    while (x > 0) {
        if ((x & 1) == 1) {
            ini = mul(matrix, ini);
        }
        matrix = mul(matrix, matrix);
        x >>= 1;
    }
    return 1*ini[0][0] + 1*ini[0][1] + 0*ini[0][2];
}

private int[][] mul(int[][] matrixA, int[][] matrixB) {
    int row = matrixA.length;
    int col = matrixB[0].length;
    int[][] res = new int[row][col];
    int size = matrixB.length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            for (int k = 0; k < size; k++) {
                res[i][j] += matrixA[i][k] * matrixB[k][j];
            }
        }
    }
    return res;
}

复杂度分析：n 是输入的整数
- 时间复杂度：$O(C^3*logn)$
- 空间复杂度：$O(C^2)$

本文作者： Chthollists
发布时间： 2022-01-17 20:17:35
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode1137.第N个泰波那契数列：「状态DP」&「矩阵快速幂」
本文链接： https://chthollists.github.io/post/ee407ebc.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！

LeetCode1137.第N个泰波那契数列：「状态DP」&「矩阵快速幂」

1. 题目描述

2. 方法一：递归 & 记忆化

3. 方法二：动态规划

4. 方法三：矩阵快速幂

\end{gathered}