C/C++ 算法入门：一维动态规划基础实战
动态规划核心概念
动态规划（Dynamic Programming）本质上是利用空间换时间，通过记录子问题的解来避免重复计算。理解它的关键在于将问题拆解为状态定义、状态转移方程、初始化和填表顺序。
简单来说，动态规划可以理解为：某种状态的公式 + 提前求出来值的容器。我们求出当前位置的值，放入容器中供后续使用。因为初始值通常是可见的，所以能启动整个推导过程。
严格来说，动态规划包含四个要素：
- 状态定义：明确
dp[i]的含义。 - 状态转移方程：描述如何从已知状态推导出当前状态。
- 初始条件：确定边界值，防止越界。
- 状态存储：通常用数组或滚动变量实现。
解题通用步骤
在实际做题中，建议遵循以下逻辑流，而不是机械地套用模板：
- 状态表示：分析题目，确定
dp[i]代表什么（例如：以 i 结尾的最优解）。 - 状态转移方程：思考
dp[i]与前面状态的关系（如dp[i-1],dp[i-2]），写出递推式。 - 初始化：根据题目要求设置起始值，确保递推不越界。
- 填表顺序：保证计算当前状态时，依赖的状态已经计算完成（通常从左到右或从上到下）。
- 返回值：根据题意从 DP 表中提取最终结果。
提示：状态表示通常为'以 i 位置结尾/开头'。初始化通常关注第一个状态，而返回值关注最后一个状态。处理数字字符判断时，务必转换为数值再比较，避免逻辑漏洞。
实战演练
下面通过四道经典题目，演示如何将上述思路落地。
1. 第 N 个泰波那契数 (Tribonacci Number)
题目链接：LeetCode 1137
思路分析： 这是一个典型的线性递推问题。我们需要找到前三个数来计算当前的数。
- 状态表示：
dp[i]表示第 i 个泰波那契数。 - 转移方程：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。 - 初始化：
dp[0]=0, dp[1]=1, dp[2]=1。 - 空间优化：由于只需要前三个数，可以使用三个变量代替数组，将空间复杂度从 O(N) 降为 O(1)。
代码实现：
class Solution {
public:
int tribonacci(int n) {
// 空间优化写法：使用滚动变量
(n == ) ;
(n == || n == ) ;
a = , b = , c = ;
ret = ;
( i = ; i <= n; ++i) {
ret = a + b + c;
a = b;
b = c;
c = ret;
}
ret;
}
};