动态规划

定义

动态规划（Dynamic Programming）是一种通过把复杂问题分解为重叠子问题、保存子问题的解来避免重复计算的算法设计方法，适用于求最优解或方案计数。

原理

使用动态规划需满足两个条件：最优子结构（大问题的最优解由子问题最优解构成）和重叠子问题（子问题被反复求解）。关键是定义状态、写出状态转移方程并确定边界。实现上有两种方式：自顶向下的记忆化递归，以及自底向上的递推填表。还可通过滚动数组等技巧压缩空间。

复杂度

• 时间复杂度：约为状态数乘以单次转移代价
• 空间复杂度：状态数，可用滚动数组优化

应用场景

• 背包问题与硬币找零
• 最长公共子序列、最长递增子序列
• 编辑距离与字符串匹配
• 路径计数与区间合并