LeetCode如何解决第N个泰波那契数的问题

# LeetCode如何解决第N个泰波那契数的问题

## 问题描述

泰波那契序列（Tribonacci Sequence）是斐波那契数列的扩展，定义如下：

T0 = 0, T1 = 1, T2 = 1, Tn+3 = Tn + Tn+1 + Tn+2 (当 n >= 0 时)

给定整数 `n`，要求计算第 `n` 个泰波那契数 `Tn` 的值。

## 解法分析

### 1. 递归法（暴力解法）

**思路**：  
直接根据定义递归计算每个泰波那契数。

**代码实现**：
```python
def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)

时间复杂度：
O(3^n)，存在大量重复计算，效率极低。
空间复杂度：
O(n)，递归栈深度为 n。

缺点：
当 n 较大时（如 n=30），运行时间会显著增加。

2. 记忆化递归（Memoization）

优化思路：
通过缓存已计算的结果避免重复计算。

代码实现：

def tribonacci(n: int, memo={}) -> int:
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    memo[n] = tribonacci(n-1, memo) + tribonacci(n-2, memo) + tribonacci(n-3, memo)
    return memo[n]

时间复杂度：
O(n)，每个子问题仅计算一次。
空间复杂度：
O(n)，需要存储 n 个结果。

3. 动态规划（迭代法）

思路：
用循环替代递归，自底向上计算泰波那契数。

代码实现：

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    a, b, c = 0, 1, 1
    for _ in range(3, n+1):
        a, b, c = b, c, a + b + c
    return c

时间复杂度：
O(n)，只需遍历一次。
空间复杂度：
O(1)，仅用常数空间存储变量。

优点：
高效且易于实现，是推荐解法。

4. 矩阵快速幂（数学优化）

思路：
利用矩阵乘法将递推关系转化为矩阵幂运算，通过快速幂算法降低时间复杂度。

数学推导：
泰波那契递推关系可表示为：

[Tn, Tn+1, Tn+2] = [Tn-1, Tn, Tn+1] * [[0, 0, 1],
                                        [1, 0, 1],
                                        [0, 1, 1]]

通过计算矩阵的 n 次幂，可直接得到 Tn。

代码实现：

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    
    def matrix_pow(mat, power):
        result = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]  # 单位矩阵
        while power > 0:
            if power % 2 == 1:
                result = matrix_multiply(result, mat)
            mat = matrix_multiply(mat, mat)
            power //= 2
        return result
    
    def matrix_multiply(a, b):
        return [
            [
                a[0][0]*b[0][0] + a[0][1]*b[1][0] + a[0][2]*b[2][0],
                a[0][0]*b[0][1] + a[0][1]*b[1][1] + a[0][2]*b[2][1],
                a[0][0]*b[0][2] + a[0][1]*b[1][2] + a[0][2]*b[2][2]
            ],
            [
                a[1][0]*b[0][0] + a[1][1]*b[1][0] + a[1][2]*b[2][0],
                a[1][0]*b[0][1] + a[1][1]*b[1][1] + a[1][2]*b[2][1],
                a[1][0]*b[0][2] + a[1][1]*b[1][2] + a[1][2]*b[2][2]
            ],
            [
                a[2][0]*b[0][0] + a[2][1]*b[1][0] + a[2][2]*b[2][0],
                a[2][0]*b[0][1] + a[2][1]*b[1][1] + a[2][2]*b[2][1],
                a[2][0]*b[0][2] + a[2][1]*b[1][2] + a[2][2]*b[2][2]
            ]
        ]
    
    mat = [[0, 0, 1], [1, 0, 1], [0, 1, 1]]
    powered_mat = matrix_pow(mat, n - 2)
    return powered_mat[0][2] + powered_mat[1][2] + powered_mat[2][2]

时间复杂度：
O(log n)，快速幂的典型复杂度。
空间复杂度：
O(1)，忽略递归栈空间。

适用场景：
当 n 极大时（如 n=1e18），此方法优势明显。

总结

推荐选择：
- 90% 的 LeetCode 用例：动态规划（简洁高效）。
- 学术研究或极端大数：矩阵快速幂。

通过此题，可以深入理解递归优化、动态规划和数学建模在算法中的应用。 “`