企业官网建设流程全解析

LeetCode-Go 题解：1137. N-th Tribonacci Number（泰波那契数）滚动数组动态规划实现解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 1137 题「N-th Tribonacci Number」展开，以仓库 LeetCode-Go 中该题目的官方题解文档 leetcode/1137.N-th-Tribonacci-Number/README.md 为骨架，结合仓库内的 Go 实现与单元测试进行纵深剖析。读者读完本文后，将掌握泰波那契数列的递推定义、使用「滚动数组」将动态规划空间复杂度优化到 O(1) 的写法，并能对照源码与测试用例完成本地验证。

题目原文与递推定义

题目要求实现函数tribonacci(n)，返回泰波那契序列（Tribonacci sequence）的第 n 项 Tn。

泰波那契序列与斐波那契（Fibonacci）最大的区别在于：每一项由前三项之和递推得到，而不是前两项之和。其完整定义如下：

• 边界条件：T0 = 0，T1 = 1，T2 = 1
• 递推关系：Tn+3 = Tn + Tn+1 + Tn+2（n >= 0）

等价地，也可以写成面向实现的形态：

Tn = Tn-1 + Tn-2 + Tn-3（n >= 3）

示例

Example 1

Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

Example 2

Input: n = 25 Output: 1389537

约束条件

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即answer <= 2^31 - 1

从约束可以看出两个关键信息：

1. n 的上限为 37，说明本仓库题解文档与实现针对的是题目给出的官方数据范围，不做超出该范围的假设；
2. 答案在 32 位整数范围内，即使用 Go 的int类型即可安全承载，无需使用int64或大数运算。由于递推中每一项约为前三项之和，增长速度为约 O(1.84^n)（泰波那契常数），n=37 时仍不溢出 32 位整数，这正是题目保证answer <= 2^31 - 1的原因。

解题思路：滚动数组动态规划

题解文档给出的思路是：「求泰波那契数列中的第 n 个数。简单题，按照题意定义计算即可。」

所谓「按照题意定义计算」，对应到代码层面就是自底向上的迭代递推：

• 维护三个变量，分别代表当前项trib以及它的前两项prev、prev2；
• 每次迭代执行trib = prev2 + prev + trib，然后整体向右滚动一格（prev2 = prev、prev = trib的旧值）；
• 循环 n-2 次后，trib即为 Tn。

这种写法本质上是动态规划的「滚动数组」优化：完整 DP 需要长度为 n+1 的数组记录每一项，但递推只依赖最近的三项，因此可以用 3 个变量代替整个数组，把空间复杂度从 O(n) 降到 O(1)。

仓库源码实现逐行解析

仓库中该题的实际实现位于 leetcode/1137.N-th-Tribonacci-Number/1137. N-th Tribonacci Number.go，完整代码如下：

package leetcode func tribonacci(n int) int { if n < 2 { return n } trib, prev, prev2 := 1, 1, 0 for n > 2 { trib, prev, prev2 = trib+prev+prev2, trib, prev n-- } return trib }

下面逐段拆解其原理：

1. 边界条件处理

if n < 2 { return n }

当 n 为 0 或 1 时，直接返回 n 本身。结合定义 T0 = 0、T1 = 1，这一句同时覆盖了两个边界情况，非常简洁。注意它没有单独处理 n = 2，因为 n = 2 时 T2 = 1 会由后面的循环逻辑正确得出。

2. 初始化三指针

trib, prev, prev2 := 1, 1, 0

这里的三元组依次表示：trib= T2 = 1，prev= T1 = 1，prev2= T0 = 0。三个变量的初始值恰好对应题目给出的三个边界项，后续循环在此基础上向右滚动。

3. 核心滚动循环

for n > 2 { trib, prev, prev2 = trib+prev+prev2, trib, prev n-- } return trib

这是整个算法的灵魂。Go 支持多重赋值，右值会先全部求值完毕再统一赋值，因此可以在一行内安全完成「计算新项 + 三个指针整体右移」：

• 新trib= 旧trib + prev + prev2（即 Tn = Tn-1 + Tn-2 + Tn-3）；
• 新prev= 旧trib（前一项变为当前项）；
• 新prev2= 旧prev（前前项向前推进一位）。

由于 Go 多重赋值的求值顺序保证，这一行不会出现传统单变量写法中「先覆盖再取旧值」的经典 bug。循环执行n - 2次后退出，此时trib即为 Tn。

4. 复杂度分析

相比递归解法（指数级时间、O(n) 栈空间）和朴素数组 DP（O(n) 空间），滚动数组写法在本题的数据范围（n <= 37）下是内存最省的迭代方案，且逻辑直观、无栈溢出风险。

测试用例验证

仓库为该题配套了表驱动单元测试，位于 leetcode/1137.N-th-Tribonacci-Number/1137. N-th Tribonacci Number_test.go。测试采用了本仓库统一的结构体模板：

type question1137 struct { para1137 ans1137 } type para1137 struct { one int } type ans1137 struct { one int }

其中para1137表示输入参数（即 n），ans1137表示期望输出（即 Tn）。测试用例覆盖了：

测试主体通过遍历用例并打印输入输出进行断言：

for _, q := range qs { _, p := q.ans1137, q.para1137 fmt.Printf("【input】:%v 【output】:%v\n", p, tribonacci(p.one)) }

其中para1137{4}→ans1137{4}、para1137{25}→ans1137{1389537}分别与题解文档中的两个 Example 完全一致，实现了「文档示例 ↔ 源码实现 ↔ 测试断言」三方互相印证。结合仓库 gotest.sh 中go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...的全量覆盖统计方式，每个题解目录都要求对应的测试保证 100% 覆盖率，本目录的两个文件恰好构成一个自洽的最小测试闭环。

与斐波那契题解的同源对照

泰波那契是斐波那契的「三项递推」推广，二者在仓库中形成了很好的对照学习素材。斐波那契第 509 题的题解位于 leetcode/0509.Fibonacci-Number/509. Fibonacci Number.go，该文件一口气给出了七种解法：

• 朴素递归（O(2^n)，仅用于理解递推本质）；
• 自底向上记忆化搜索（数组缓存，O(n) 空间）；
• 自顶向下记忆化搜索（递归 + map 缓存）；
• 滚动数组 DP（与 1137 题同思路，O(1) 空间）；
• 矩阵快速幂（O(log n)）；
• 通项公式法（浮点运算，涉及黄金分割）；
• 协程并发版（源码注释明确指出启动 goroutine 极慢，仅作反面教材）。

对照阅读可以清晰看出：当递推依赖的项数从 2 增加到 3 时，滚动数组变量从 2 个增加到 3 个，其余递推框架完全一致。1137 题选用最简的滚动数组解法，正是「按照题意定义计算」的直译；而 509 题的多解法清单则展示了同一类递推问题在不同场景下的优化阶梯（时间换空间、矩阵幂换时间）。

本地运行与验证方式

仓库使用 Go 1.19（见 go.mod）。在仓库根目录下，可以单独运行本题的测试：

go test ./leetcode/1137.N-th-Tribonacci-Number/ -v -run Test_Problem1137

也可以运行整个 leetcode 包的覆盖测试，生成覆盖率报告：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

通过-v参数可以看到测试输出，例如：

【input】:4 【output】:4 【input】:25 【output】:1389537

输出与题解文档中的 Example 1、Example 2 完全吻合，验证通过。

小结

本文完整覆盖了 题解文档 中的题目定义、两个示例与约束条件，并在此基础上深挖了仓库的 Go 实现：三个指针的滚动数组动态规划，时间复杂度 O(n)、空间复杂度 O(1)；同时结合表驱动测试用例与斐波那契姊妹题做了横向对照。掌握了这道题，你就掌握了「k 项递推 + 滚动数组」这一类动态规划题目的通用套路——把依赖的 k 个历史状态压缩为 k 个变量，即可用 O(n) 时间、O(1) 空间求解。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go