题目描述
T0=0, T1=1, T2=1，之后 Tn = Tn−1 + Tn−2 + Tn−3，求第 n 个。
n = 4
输出 = 4 （0,1,1,2,4）
思路解析
直接递归 T(n)=T(n-1)+T(n-2)+T(n-3) 会把小项算无数遍，指数爆炸。咱用一排 dp 把每项算一次记下来，从前往后推。
先填好前三项 0、1、1，之后每一项都是前三项之和。一路填到 dp[n]。
初始三项：种子项：T0=0、T1=1、T2=1，先填好。
算 T3：T3 = 前三项之和 0+1+1 = 2。
算 T4：T4 = 1+1+2 = 4，就是答案。
只依赖前几项的线性递推，都能用「填表 → 滚动变量」把空间降到 O(1)：斐波那契、爬楼梯、泰波那契一脉相承。
参考代码（Python）
Python
1if n == 0: return 0
2if n < 3: return 1
3a, b, c = 0, 1, 1 # 前三项滚动
4for _ in range(3, n + 1):
5 a, b, c = b, c, a + b + c # 一起往前挪
6return c复杂度分析
- 时间复杂度：O(n) —— 从前往后算一遍
- 空间复杂度：O(1) —— 三个滚动变量
套路模板
记住骨架：只保留递推需要的最近几项、循环里算新值并整体前移。依赖前 k 项就用 k 个变量。
Python
1# dp[i] 只依赖前 k 项时
2初始化前 k 项的几个变量
3for i in range(k, n + 1):
4 新 = f(前几个变量) # 递推式
5 一起向前滚动这几个变量
6return 最后一个易错点
- ❌ 没处理 n=0,1,2 的种子 → ✅ 先特判小 n（递推从第 3 项才开始）
- ❌ 滚动赋值分开写 → ✅ 用元组同时赋值（分开写会用到已被覆盖的旧值）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。