1137. 第 N 个泰波那契数-LeetCode

🎯 问题描述（来源于LeetCode）

描述：泰波那契序列 Tn 定义如下：

说明：

  • 答案保证在 32 位有符号整数范围内（即 [−231,231−1][-2^{31}, 2^{31} - 1]）。

  • 示例：

  • 示例 1：

1
2
3
4
5
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
  • 示例 2：
1
2
输入：n = 25
输出：1389537

💻 解题思路

核心思想：
泰波那契数列是斐波那契数列的变种，同样具有明显的重叠子问题性质。如果使用朴素递归（直接函数调用自己），时间复杂度将是指数级的，导致超时。
为了解决这个问题，我们采用记忆化搜索（动态规划的自顶向下实现）：

  1. 查表：在计算前，先检查该状态是否已经计算过。
  2. 计算：如果未计算过，递归计算其依赖的前三个状态之和。
  3. 存表：计算出结果后，立即将其存入哈希表（字典）中，供后续调用复用。

算法步骤：

  1. 初始化一个字典 table，预存基准情况（T0,T1,T2T_0, T_1, T_2）。
  2. 定义递归函数 dp(i)：
    • 如果 i 在 table 中，直接返回 table[i]。
    • 否则，计算 dp(i-1) + dp(i-2) + dp(i-3)。
    • 将计算结果存入 table[i] 并返回。
  3. 调用 dp(n) 并返回结果。

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def tribonacci(self, n: int) -> int:
        # 1. 初始化备忘录 (字典)，存储已知的基础情况
        table = {0: 0, 1: 1, 2: 1}
        
        def dp(i: int) -> int:
            # 2. 查表：如果这个问题之前算过（或者是基础情况），直接返回
            if i in table:
                return table[i]
            
            # 3. 计算：状态转移方程
            # 注意：这里调用的是 dp 函数，而不是直接访问 table 键
            # 这样能保证如果 i-1 等未计算，会自动触发递归计算
            cnt = dp(i-1) + dp(i-2) + dp(i-3)
            
            # 4. 存储：将新算出的结果存入字典
            table[i] = cnt
            return cnt
            
        return dp(n)

思路1：📊 性能分析

提交结果

  • 运行时间：0ms击败100.00%
  • 内存消耗：19.13MB击败40.66%

复杂度验证

  • 时间复杂度： O(N)O(N)
    • 解析：每个状态 i 从 0 到 n 最多只会被计算一次。后续的重复访问都是通过字典 O(1)O(1) 查找完成的。
  • 空间复杂度： O(N)O(N)
    • 解析：主要由两部分组成。一是递归调用栈的深度，最深为 O(N)O(N) ；二是字典 table 存储了 NN 个键值对，空间为 O(N)O(N) 。

思考

  1. 为什么不能直接写 table[i-1]？
    • 在代码逻辑中，必须调用 dp(i-1) 而不是直接访问 table[i-1]。因为如果直接访问 table[i-1]，而 i-1 还没有被存入字典（即尚未计算），Python 会直接抛出 KeyError。而调用 dp(i-1) 函数，函数内部会自动处理“查表-计算-存表”的完整逻辑，保证了安全性。
  2. 递归 vs 迭代：
    • 这种写法是自顶向下的（Top-Down）。它更符合人类的直觉（从结果反推条件）。