泰波那契数 图解题解

这道题到底在问什么

n

6

输出

13

过程

0,1,1,2,4,7,13

最优解：一步一步想明白

1. 3最直接的写法是递归 T(n)=T(n−1)+T(n−2)+T(n−3)。但算 T6 要算 T5、T4、T3，算 T5 又要算 T4、T3……同一个 T3 被反复展开，调用次数指数级膨胀，n 稍大就卡死。慢就慢在重复子问题。
2. 4既然小项被重复算，那就用一排 dp 把每一项的答案记下来，从左往右只算一次。状态 dp[i] = 第 i 个泰波那契数；转移就是把前三项加起来。为什么能这么记？因为 dp[i] 只依赖固定的前三格，前面算好了，后面直接查表，不必重算——这就是重叠子问题变递推。
3. 5T0,T1,T2 = 0,1,1先把题目给的种子项填进表：T0=0、T1=1、T2=1。后面四格还空着，等会儿一格一格往右推。表固定 1 行 7 列，全程只覆盖数值、不增删格子。
4. 6下一个要算 T3从最左边第一个空格 T3 开始填。它的三个依赖格（T0、T1、T2，蓝色）都已经算好在左边了，所以能直接相加得到它——这就是「从左往右填表」的核心节奏。
5. 7T3 = 0+1+1 = 2第一格要算的是 T3。它依赖左边三格 T0、T1、T2（蓝色），直接读表相加 = 0+1+1 = 2。注意：这里不再递归展开，三个依赖都是查表得来的，这就是省下重复计算的转折点。
6. 8T4 = 1+1+2 = 4窗口往右滑一格：T4 依赖 T1、T2、T3 = 1+1+2 = 4。其中 T3 是上一步刚算好记下来的，现在直接拿来用，不重算。
7. 9T5 = 1+2+4 = 7继续：T5 依赖 T2、T3、T4 = 1+2+4 = 7。每往右一格，依赖的三格也整体右移一位。
8. 10T6 = 2+4+7 = 13最后一格 T6 依赖 T3、T4、T5 = 2+4+7 = 13。整张表从左推到右，每格只算一次。
9. 11漏 T3 → T6 算成 11负例提醒：泰波那契是前三项相加。如果手滑写成像斐波那契那样只加前两项（T4+T5=11），就会漏掉被框住的 T3=2，答案直接错。三个依赖格一个都不能少。
10. 12dp[6] = 13表格最右一格 dp[6] = 13 就是答案：第 6 个泰波那契数。
11. 15只依赖前几项的线性递推，都能用「填表 → 一格一格往右推」解决：斐波那契、爬楼梯、泰波那契一脉相承。把大问题拆成「前几项已知的小问题」，正是 DP 的起点。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def tribonacci(self, n):
        if n == 0:
            return 0
        if 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

dp = [0] * (n + 1)
dp[前 k 项] = 初始种子                 # 递推的起点
for i in range(k, n + 1):
    dp[i] = f(dp[i-1], ..., dp[i-k])  # 用前 k 项递推
return dp[n]

复杂度

面试官可能追问