动态规划入门：从斐波那契到泰波那契与三步问题

1. 动态规划入门：从斐波那契到泰波那契

动态规划（Dynamic Programming）作为算法设计中的重要方法论，其核心思想是通过将复杂问题分解为相互重叠的子问题来提升计算效率。让我们从一个经典的入门案例开始——泰波那契数列问题。

1.1 问题定义与数学建模

泰波那契数列（Tribonacci Sequence）是斐波那契数列的扩展版本，其递推关系定义为：
T₀ = 0, T₁ = 1, T₂ = 1
Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃ （当 n ≥ 3 时）

这个问题看似简单，但直接使用递归实现会导致指数级的时间复杂度。以计算T(5)为例：
T(5) = T(4) + T(3) + T(2)
T(4) = T(3) + T(2) + T(1)
T(3) = T(2) + T(1) + T(0)
...
可以看到T(3)被重复计算了多次。

1.2 动态规划四步法

1.2.1 状态表示

我们定义dp[i]表示第i个泰波那契数的值。这种定义直接对应问题需求，是最直观的状态表示方式。

1.2.2 状态转移方程

根据数列定义直接得出：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

1.2.3 初始化

需要预先设置前三个值：
dp[0] = 0
dp[1] = dp[2] = 1

1.2.4 填表顺序

由于每个状态依赖于前三个状态，自然采用从左到右的顺序填充dp表。

1.3 空间优化技巧

基础实现需要O(n)空间存储整个dp数组。观察发现，当前状态只依赖前三个状态，因此可以采用滚动数组技术将空间复杂度优化到O(1)：

cpp复制int tribonacci(int n) {
    if(n == 0) return 0;
    if(n == 1 || n == 2) return 1;
    
    int a = 0, b = 1, c = 1, d;
    for(int i = 3; i <= n; ++i) {
        d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return d;
}

注意：边界条件