动态规划基础
动态规划（Dynamic Programming）的核心在于将复杂问题分解为重叠子问题，通过存储中间状态避免重复计算。简单来说，它包含两个要素：某种状态的公式 + 提前求出来值的容器。我们计算出当前位置的值放入容器中供后续使用，初始值通常由题目直接给出。
严格定义下：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 状态存储
解题五步法
掌握以下五个步骤，能帮助你系统性地解决大部分 DP 问题：
- 状态表示：明确
dp[i]的含义。通常结合经验与题目要求，例如'以 i 位置结尾'或'前 i 个元素的最优解'。 - 状态转移方程：这是最关键的一步，本质是推导
dp[i] = ?。需根据状态表示和题目逻辑找出当前状态与前序状态的关系。 - 初始化：确保填表时不越界，并根据题目设定初始值（如
dp[0],dp[1]）。 - 填表顺序：保证计算当前状态时，所需的前置状态已计算完成。通常是从左向右或从上到下。
- 返回值：根据题意从 dp 表中提取最终结果。
提示：处理边界问题时，适当开辟额外空间（如多开一位）往往能简化代码逻辑。判断多位数字时，建议转换为数值而非单纯字符比较，以避免不可控的边界情况。
实战演练
1. 第 N 个泰波那契数
题目描述：计算第 n 个泰波那契数，其中 T(0)=0, T(1)=1, T(2)=1, T(n)=T(n-1)+T(n-2)+T(n-3)。
思路分析：
这是一个典型的一维 DP 问题。状态表示很直观，dp[i] 即为第 i 个泰波那契数。转移方程直接由定义得出。由于计算 dp[i] 只需要前三个值，我们可以进行空间优化。
核心代码：
class Solution {
public:
int tribonacci(int n) {
// 空间优化写法：仅保留前三个变量
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int a = 0, b = 1, c = 1;
int ret = 0;
for ( i = ; i <= n; ++i) {
ret = a + b + c;
a = b;
b = c;
c = ret;
}
ret;
}
};
