迭代法求 Tribonacci 数
Iterative Tribonacci Number
开始编码Tribonacci 序列是 Fibonacci 的三项推广：T_0 = 0，T_1 = 1，T_2 = 1，对 n ≥ 3 有 T_n = T_{n-1} + T_{n-2} + T_{n-3}。它在组合数学里很常见（铺砖计数、由 1/2/3 构成的合成数），也是面试线性递推 DP 题里 Fibonacci 之后的标准下一站。它单独成题的原因纯属机械：新手第一反应要么是写指数级三叉递归，要么是开整段长度的数组；而递推每次只用到最后三个值，所以滚动三变量更新就够了——O(n) 时间、O(1) 空间。
请实现 solution(n: int) -> int，返回 T_n。
边界。 n == 0 返回 0，n == 1 返回 1，n == 2 返回 1，三种情况直接处理。迭代。 初始化 a, b, c = 0, 1, 1，分别对应 (T_0, T_1, T_2)。让 i 从 3 一直到 n（含），每步算 nxt = a + b + c，再 a, b, c = b, c, nxt。循环结束时 c 就是 T_n。整个过程共 n - 2 次加法，无论 n 多大都只用三个整数槽。
例子
solution(0) 返回 0，solution(1) 返回 1，solution(2) 返回 1——三个显式基础 case，循环根本不会进入。
solution(4) 返回 4。手算一下：T_3 = 0 + 1 + 1 = 2，T_4 = 1 + 1 + 2 = 4。这是抓 off-by-one 初始化错误最经典的小用例。
solution(25) 返回 1389537。n = 25 时数值已经到了百万级，朴素无记忆递归在这里完全没法跑（最坏 3^25 ≈ 8.5 × 10^11 次调用），而滚动窗口只需要 23 次加法。这条用例就是用来分清 O(1) 空间迭代解和那些试图硬算递归的写法。
实践背景
迭代 Tribonacci 是线性递推 DP 家族里最干净的入门题，而这一族悄悄撑起了相当一大块的量化和基建面试题：Fibonacci 本身、爬楼梯（其实就是步长 1/2/3 的 Tribonacci）、打家劫舍、解码方法，以及任何形如「给定局部转移，问到达状态 n 的方案数」的问题。形状永远一样——最近若干状态构成的小固定窗口、O(1) 空间的滚动更新、对那些深度短于递推阶数的边界情况显式处理。养成滚动窗口的习惯之后，对那些其实只用最近三个值的题目你就不会再无脑开 O(n) 的 DP 数组；同样的套路也直接迁移到离散时间定价递推和有限记忆长度的信号滤波器上。
约束条件
- 0 ≤ n ≤ 37
- 结果为精确整数——不用浮点容差
- 使用 O(1) 额外空间（三变量滚动更新）；朴素递归是指数级，会在大测试用例上超时
- `n ≤ 37` 时所有 `T_n` 都稳稳落在 64 位有符号整数范围内，无需大整数处理
样例
Case 1 · base case n=0 — explicit zero
输入: [0]
期望: 0
递推的零阶基础值，T_0 = 0，必须在循环之前显式返回，否则任何用 a,b,c=0,1,1 起步的迭代都会少处理这条 case。
Case 2 · base case n=1 — first ones
输入: [1]
期望: 1
第二个基础值 T_1 = 1。和 T_2 = 1 一样必须在循环之前返回，确认基础值表写对了。
Case 3 · base case n=2 — second one
输入: [2]
期望: 1
第三个基础值 T_2 = 1。Tribonacci 的特殊之处在于这里也是 1（不像 Fibonacci T_2 = 1, T_3 = 2 是不同的两阶），所以三个 base case 全部单独验证。
Case 4 · first recurrence step n=3 — T_3 = 0+1+1 = 2
输入: [3]
期望: 2
第一次进入循环：T_3 = T_0 + T_1 + T_2 = 0 + 1 + 1 = 2。这是验证循环初值 a,b,c = 0,1,1 是否对位的最关键用例——若初值偏一格写成 1,1,2，这里会错为 4。
Case 5 · larger n=25 — separates iterative from naive recursion
输入: [25]
期望: 1389537
n = 25 时朴素无记忆递归已经爆炸（最坏约 8.5e11 次调用），而滚动窗口只要 23 次加法。结果 1,389,537 是分清两种解法最直接的卡口。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · base case n=0 — explicit zero
输入: [0]
期望: 0
递推的零阶基础值，T_0 = 0，必须在循环之前显式返回，否则任何用 a,b,c=0,1,1 起步的迭代都会少处理这条 case。
Case 2 · base case n=1 — first ones
输入: [1]
期望: 1
第二个基础值 T_1 = 1。和 T_2 = 1 一样必须在循环之前返回，确认基础值表写对了。
Case 3 · base case n=2 — second one
输入: [2]
期望: 1
第三个基础值 T_2 = 1。Tribonacci 的特殊之处在于这里也是 1（不像 Fibonacci T_2 = 1, T_3 = 2 是不同的两阶），所以三个 base case 全部单独验证。
Case 4 · first recurrence step n=3 — T_3 = 0+1+1 = 2
输入: [3]
期望: 2
第一次进入循环：T_3 = T_0 + T_1 + T_2 = 0 + 1 + 1 = 2。这是验证循环初值 a,b,c = 0,1,1 是否对位的最关键用例——若初值偏一格写成 1,1,2，这里会错为 4。
Case 5 · larger n=25 — separates iterative from naive recursion
输入: [25]
期望: 1389537
n = 25 时朴素无记忆递归已经爆炸（最坏约 8.5e11 次调用），而滚动窗口只要 23 次加法。结果 1,389,537 是分清两种解法最直接的卡口。