一、动态规划基础概念

动态规划（Dynamic Programming，简称DP） 是解决多阶段决策过程优化问题的通用方法，通过将多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系逐个求解。

动态规划的三个关键特性：

1. 无后效性：某阶段状态一旦确定，就不受后续决策影响

2. 最优子结构：问题的最优解包含的子问题的解也是最优的

3. 重叠子问题：子问题之间不独立，可能被多次使用

二、动态规划解题步骤

1. 划分阶段：考察问题是否满足无后效性。

2. 定义状态变量：明确子问题的表示方式。

3. 写出状态转移方程：建立递推关系式。

4. 确定边界条件：明确已知解。

5. 代码实现：可用记忆化递归或递推方式实现。