前言
斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。希望通过本研究，为算法设计爱好者提供启发，并在实际问题中应用该技术。
一、1137. 第 N 个泰波那契数
题目链接：https://leetcode.cn/problems/n-th-tribonacci-number/description/
1. 题目解析
Tribonacci 数列是一个递归数列，类似于斐波那契数列，但它的递推公式是：
- 递推公式：
T(n) = T(n-1) + T(n-2) + T(n-3)，对于n >= 3； - 初始条件：
T(0) = 0T(1) = 1T(2) = 1
需要实现一个函数 tribonacci(int n)，返回第 n 个 Tribonacci 数。
2. 讲解算法原理
状态表示
设 dp[i] 表示第 i 个 Tribonacci 数，即前 i 个数的第三阶斐波那契数列。换句话说，dp[i] 是定义如下的递推关系：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3。
状态转移方程
根据题目描述，Tribonacci 数列满足：
dp[0] = 0dp[1] = 1dp[2] = 1dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3
初始化
初始化初始条件，保证在填写表格的时候不会越界：
dp[0] = 0dp[1] = 1dp[2] = 1
填表顺序
从 i = 3 开始递推填表，因为计算 dp[i] 时，需要依赖 dp[i-1], dp[i-2], 和 dp[i-3] 的值，这些值在计算当前状态时必须已知。因此：
- 填写顺序是从
i = 3开始递增。
返回值
最后返回 dp[n]，即第 n 个 Tribonacci 数。
3. 编写代码
class Solution {
public:
{
(n == ) ;
(n == || n == ) ;
;
dp[] = , dp[] = dp[] = ;
( i = ; i <= n; i++) {
dp[i] = dp[i] + dp[i] + dp[i];
}
dp[n];
}
};
