泰波那契数

最直接的写法是递归 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 的起点。