题目描述
T0=0, T1=1, T2=1，之后 Tn = Tn−1 + Tn−2 + Tn−3，求第 n 个。
思路解析
最直接的写法是递归 T(n)=T(n−1)+T(n−2)+T(n−3)。但算 T6 要算 T5、T4、T3，算 T5 又要算 T4、T3……同一个 T3 被反复展开，调用次数指数级膨胀，n 稍大就卡死。慢就慢在重复子问题。
既然小项被重复算，那就用一排 dp 把每一项的答案记下来，从左往右只算一次。状态 dp[i] = 第 i 个泰波那契数；转移就是把前三项加起来。为什么能这么记？因为 dp[i] 只依赖固定的前三格，前面算好了，后面直接查表，不必重算——这就是重叠子问题变递推。
建表 · 种子三项：先把题目给的种子项填进表：T0=0、T1=1、T2=1。后面四格还空着，等会儿一格一格往右推。表固定 1 行 7 列，全程只覆盖数值、不增删格子。
第一个待填格：从最左边第一个空格 T3 开始填。它的三个依赖格（T0、T1、T2，蓝色）都已经算好在左边了，所以能直接相加得到它——这就是「从左往右填表」的核心节奏。
算 T3：第一格要算的是 T3。它依赖左边三格 T0、T1、T2（蓝色），直接读表相加 = 0+1+1 = 2。注意：这里不再递归展开，三个依赖都是查表得来的，这就是省下重复计算的转折点。
算 T4：窗口往右滑一格：T4 依赖 T1、T2、T3 = 1+1+2 = 4。其中 T3 是上一步刚算好记下来的，现在直接拿来用，不重算。
算 T5：继续：T5 依赖 T2、T3、T4 = 1+2+4 = 7。每往右一格，依赖的三格也整体右移一位。
算 T6 · 最后一格：最后一格 T6 依赖 T3、T4、T5 = 2+4+7 = 13。整张表从左推到右，每格只算一次。
对比 · 若漏一项就错：负例提醒：泰波那契是前三项相加。如果手滑写成像斐波那契那样只加前两项（T4+T5=11），就会漏掉被框住的 T3=2，答案直接错。三个依赖格一个都不能少。
答案：表格最右一格 dp[6] = 13 就是答案：第 6 个泰波那契数。
只依赖前几项的线性递推，都能用「填表 → 一格一格往右推」解决：斐波那契、爬楼梯、泰波那契一脉相承。把大问题拆成「前几项已知的小问题」，正是 DP 的起点。
参考代码（Python）
1def tribonacci(self, n):
2 if n == 0: return 0 # 种子特判
3 if n < 3: return 1 # T1=T2=1
4 dp = [0] * (n + 1)
5 dp[0], dp[1], dp[2] = 0, 1, 1 # 填三个种子项
6 for i in range(3, n + 1): # 从第 3 项推到第 n 项
7 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] # 前三项之和
8 return dp[n]复杂度分析
- 时间复杂度：O(n) —— 从左到右填表，每格做一次三数相加
- 空间复杂度：O(n) —— dp 数组存 n+1 项；只保留前三项可降到 O(1)
套路模板
记住骨架：填好前 k 个种子项，循环里 dp[i] 由前 k 项算出。依赖前几项就读前几格，斐波那契读 2 格、泰波那契读 3 格。
1dp = [0] * (n + 1)
2dp[前 k 项] = 初始种子 # 递推的起点
3for i in range(k, n + 1):
4 dp[i] = f(dp[i-1], ..., dp[i-k]) # 用前 k 项递推
5return dp[n]易错点
- 错误写法：dp[i] = dp[i-1] + dp[i-2]（漏第三项） → 正确写法：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]（泰波那契是前三项之和，少加 dp[i-3] 会算出错值（如 T6 错成 11））
- 错误写法：没填种子 dp[0]=0,dp[1]=1,dp[2]=1 就开循环 → 正确写法：先把前三项种子填好再从 i=3 推（递推从第 3 项才开始，种子没设会让后面全部错位）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。