【什么是动态规划】动态规划（Dynamic Programming，简称 DP）是一种用于解决复杂问题的算法设计方法。它通过将问题分解为更小的子问题，并存储这些子问题的解以避免重复计算，从而提高效率。动态规划广泛应用于计算机科学、数学、经济学等领域，尤其适合处理具有重叠子问题和最优子结构的问题。
一、动态规划的核心概念
| 概念 | 定义 |
| 最优子结构 | 一个问题的最优解包含其子问题的最优解。 |
| 重叠子问题 | 在递归求解过程中，某些子问题会被多次调用，可以通过存储结果来优化。 |
| 状态转移方程 | 描述当前状态与之前状态之间的关系，是动态规划的关键部分。 |
| 备忘录/数组 | 存储已计算过的子问题的解，避免重复计算。 |
二、动态规划的基本步骤
1. 识别问题是否具备动态规划的特性
确认问题是否具有最优子结构和重叠子问题。
2. 定义状态
将问题分解为若干个状态，每个状态代表一个特定的子问题。
3. 建立状态转移方程
找出不同状态之间的关系，写出递推公式。
4. 初始化边界条件
设定最简单情况下的初始值，作为递推的起点。
5. 计算并存储结果
按照状态转移方程逐步计算，将结果存储在数组或表中。
6. 返回最终结果
根据问题需求，从存储的结果中提取最终答案。
三、动态规划的典型应用场景
| 应用场景 | 说明 |
| 最长公共子序列（LCS） | 找出两个字符串中共同存在的最长子序列。 |
| 背包问题 | 在有限容量下选择物品，使总价值最大。 |
| 斐波那契数列 | 使用动态规划优化递归实现，减少重复计算。 |
| 最短路径问题 | 如 Dijkstra 算法中的某些变种。 |
| 矩阵链乘法 | 优化多个矩阵相乘的顺序，减少运算次数。 |
四、动态规划的优缺点
| 优点 | 缺点 |
| - 避免重复计算，提高效率 | - 需要额外的空间存储中间结果 |
| - 适用于有重叠子问题的问题 | - 状态转移方程的构建可能较为复杂 |
| - 可以得到全局最优解 | - 对于大规模问题可能需要优化 |
五、动态规划与分治法的区别
| 特性 | 动态规划 | 分治法 |
| 子问题是否重叠 | 是 | 否 |
| 是否存储子问题解 | 是 | 否 |
| 时间复杂度 | 较低 | 较高（可能指数级） |
| 适用问题类型 | 有重叠子问题的问题 | 无重叠子问题的问题 |
六、总结
动态规划是一种高效的算法设计方法，特别适用于具有重叠子问题和最优子结构的问题。通过合理地定义状态和状态转移方程，可以有效降低时间复杂度，提升程序运行效率。尽管实现上需要一定的思考和设计，但其在实际应用中具有广泛的用途，是解决复杂问题的重要工具之一。
