好的，我们来分别解决这两个使用动态规划（Dynamic Programming, DP）的经典问题。

第001题：第N个泰波拉契数 (N-th Tribonacci Number)

问题描述： 泰波拉契数列定义如下： $T_0 = 0$, $T_1 = 1$, $T_2 = 1$， 且对于 $n \geq 3$，满足： $$T_n = T_{n-1} + T_{n-2} + T_{n-3}$$ 请计算第 $n$ 个泰波拉契数 $T_n$。

动态规划思路：

1. 状态定义： dp[i] 表示第 $i$ 个泰波拉契数 $T_i$。
2. 边界条件：
   • dp[0] = 0
   • dp[1] = 1
   • dp[2] = 1
3. 状态转移方程： $$dp[i] = dp[i-1] + dp[i-2] + dp[i-3] \quad \text{for} \quad i \geq 3$$
4. 计算顺序： 从小到大计算 dp[3] 到 dp[n]。

C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

int tribonacci(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    return dp[n];
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    cout << "Tribonacci(" << n << ") = " << tribonacci(n) << endl;
    return 0;
}

时间复杂度： $O(n)$
空间复杂度： $O(n)$（可优化至 $O(1)$ 使用滚动数组）

第002题：三步问题 (Three Steps Problem)

问题描述： 一个小孩上楼梯，每次可以走 $1$ 阶、$2$ 阶或 $3$ 阶。楼梯共有 $n$ 阶。请计算有多少种不同的方式可以爬到楼顶。结果可能很大，返回结果模 $1000000007$。

动态规划思路：

1. 状态定义： dp[i] 表示到达第 $i$ 阶楼梯的方案数。
2. 边界条件：
   • dp[0] = 1（不爬也是一种方案）
   • dp[1] = 1（只有 $1$ 种方式：走 $1$ 阶）
   • dp[2] = 2（$2$ 种方式：$1+1$ 或 $2$）
3. 状态转移方程： $$dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) \mod 1000000007 \quad \text{for} \quad i \geq 3$$
4. 计算顺序： 从小到大计算 dp[3] 到 dp[n]。

C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int waysToStep(int n) {
    if (n == 0 || n == 1) return 1;
    if (n == 2) return 2;
    
    vector<long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD;
    }
    return dp[n];
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    cout << "Ways to climb " << n << " steps: " << waysToStep(n) << endl;
    return 0;
}

时间复杂度： $O(n)$
空间复杂度： $O(n)$（可优化至 $O(1)$ 使用滚动数组）

总结

动态规划的核心在于：

1. 定义状态
2. 找到边界条件
3. 建立状态转移方程
4. 按顺序计算状态值

这两个问题通过递推关系清晰地展示了动态规划的高效性。