动态规划实战：泰波拉契数与爬楼梯

好的，我们来分别解决这两个使用动态规划（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$。

动态规划思路：

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;
}

https://www.zhihu.com/zvideo/1996824873880793438
https://www.zhihu.com/zvideo/1996824669249103117
https://www.zhihu.com/zvideo/1996824525061497543
https://www.zhihu.com/zvideo/1996824421915186815
https://www.zhihu.com/zvideo/1996824147616084565
https://www.zhihu.com/zvideo/1996824042569761003
https://www.zhihu.com/zvideo/1996823907588649933
https://www.zhihu.com/zvideo/1996823716269691484
https://www.zhihu.com/zvideo/1996823539890816144
https://www.zhihu.com/zvideo/1996823300052104035
https://www.zhihu.com/zvideo/1996823083781207297
https://www.zhihu.com/zvideo/1996822840524183334
https://www.zhihu.com/zvideo/1996823209845219472
https://www.zhihu.com/zvideo/1996823419501703876
https://www.zhihu.com/zvideo/1996822717488443813
https://www.zhihu.com/zvideo/1996822476718641996
https://www.zhihu.com/zvideo/1996822241128760991
https://www.zhihu.com/zvideo/1996822107322095155
https://www.zhihu.com/zvideo/1996821857735836576

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

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

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

动态规划思路：

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;
}

https://www.zhihu.com/zvideo/1996824873880793438
https://www.zhihu.com/zvideo/1996824669249103117
https://www.zhihu.com/zvideo/1996824525061497543
https://www.zhihu.com/zvideo/1996824421915186815
https://www.zhihu.com/zvideo/1996824147616084565
https://www.zhihu.com/zvideo/1996824042569761003
https://www.zhihu.com/zvideo/1996823907588649933
https://www.zhihu.com/zvideo/1996823716269691484
https://www.zhihu.com/zvideo/1996823539890816144
https://www.zhihu.com/zvideo/1996823300052104035
https://www.zhihu.com/zvideo/1996823083781207297
https://www.zhihu.com/zvideo/1996822840524183334
https://www.zhihu.com/zvideo/1996823209845219472
https://www.zhihu.com/zvideo/1996823419501703876
https://www.zhihu.com/zvideo/1996822717488443813
https://www.zhihu.com/zvideo/1996822476718641996
https://www.zhihu.com/zvideo/1996822241128760991
https://www.zhihu.com/zvideo/1996822107322095155
https://www.zhihu.com/zvideo/1996821857735836576

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

总结

动态规划的核心在于：

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