动态规划入门：泰波那契数列与三步问题解析

1. 动态规划与斐波那契数列模型的关系

动态规划作为算法设计中的重要方法论，其核心思想是将复杂问题分解为相互重叠的子问题。斐波那契数列问题堪称动态规划最经典的入门案例，它完美展现了动态规划"记忆化存储"和"子问题复用"的两大特征。

泰波那契数列是斐波那契数列的扩展形式，定义为：
T0 = 0, T1 = 1, T2 = 1
Tn = Tn-1 + Tn-2 + Tn-3 （当 n >= 3 时）

这个定义本身就揭示了问题的递归结构——当前状态依赖于前三个状态的组合。当我们计算T(5)时，需要先计算T(4)、T(3)、T(2)，而计算T(4)又需要T(3)、T(2)、T(1)，其中T(3)等子问题会被重复计算。

关键观察：使用纯递归解法时，时间复杂度会达到O(3^n)，因为每个问题会分解为三个子问题。而动态规划通过存储中间结果，可以将复杂度降至O(n)。

2. 第N个泰波那契数的解法实现

2.1 基础动态规划解法

最直接的实现方式是使用一维数组存储中间结果：

python复制def tribonacci(n: int) -> int:
    if n == 0: return 0
    if n <= 2: return 1
    
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 0, 1, 1
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
    return dp[n]

这个实现有几个值得注意的细节：

1. 边界条件处理：n=0和n=1/2的情况需要单独处理
2. 数组初始化：长度设为n+1以包含0到n所有索引
3. 递推顺序：必须从小到大计算，确保子问题先被解决

2.2 空间优化版本

观察到当前状态只依赖前三个状态，可以优化空间复杂度到O(1)：

python复制def tribonacci(n: int) -> int:
    if n == 0: return 0
    a, b, c = 0, 1, 1
    
    for _ in range(3, n + 1):
        a, b, c = b