【什么是动态规划】动态规划（Dynamic Programming，简称 DP）是一种用于解决复杂问题的算法设计方法，特别适用于具有重叠子问题和最优子结构性质的问题。它通过将问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算，从而提高效率。
动态规划的核心思想是“分而治之”，但与传统的分治法不同，动态规划会记录并复用已经求解的子问题结果，从而减少时间复杂度。
动态规划总结
| 项目 | 内容 |
| 定义 | 动态规划是一种通过将大问题分解为更小的子问题，并存储这些子问题的解来优化整体解决方案的算法设计方法。 |
| 适用条件 | - 子问题重叠 - 最优子结构（即原问题的最优解包含子问题的最优解） |
| 特点 | - 自底向上求解 - 记忆化存储中间结果 - 避免重复计算 |
| 常见应用场景 | - 最短路径问题（如Floyd算法） - 背包问题 - 斐波那契数列 - 字符串编辑距离 - 最长公共子序列等 |
| 优点 | - 提高算法效率，减少重复计算 - 解决复杂问题时更高效 |
| 缺点 | - 空间复杂度较高（需要存储中间结果） - 对于某些问题，难以识别是否适合使用动态规划 |
| 常用策略 | - 递归 + 记忆化（自顶向下） - 迭代 + 表格填充（自底向上） |
动态规划与分治法的区别
| 比较项 | 动态规划 | 分治法 |
| 子问题是否重叠 | 是 | 否 |
| 求解方式 | 自底向上或记忆化 | 自顶向下 |
| 存储中间结果 | 是 | 否 |
| 时间复杂度 | 通常较低 | 可能较高（如无优化） |
| 适用场景 | 有重叠子问题的问题 | 无重叠子问题的问题 |
总结
动态规划是一种强大的算法工具，尤其在处理具有重叠子问题和最优子结构的问题时表现出色。虽然它需要额外的空间来存储中间结果，但在许多实际应用中，其效率优势明显。掌握动态规划的关键在于识别问题是否具备上述两个特性，并选择合适的求解方式（递归或迭代）。
