动态规划

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的算法思想。

基本概念

核心思想

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：子问题会重复出现，可以保存子问题的解
3. 无后效性：某阶段的状态确定后，后续状态的演变不再受此前各状态及决策的影响

解题步骤

1. 确定状态和选择
2. 明确 dp 数组的定义
3. 找出状态转移方程
4. 确定初始条件和边界情况
5. 确定遍历顺序

常见类型

线性 DP

1. 单序列问题

   • 最长上升子序列
   • 最大子数组和
   • 打家劫舍

2. 双序列问题

   • 最长公共子序列
   • 编辑距离
   • 正则表达式匹配

区间 DP

• 最长回文子序列
• 戳气球
• 矩阵链乘法

背包 DP

1. 0-1背包
2. 完全背包
3. 多重背包
4. 分组背包

状态压缩 DP

• 旅行商问题
• 集合划分问题
• 状态表示与压缩

树形 DP

• 树的最大独立集
• 树的最小支配集
• 树的直径

数位 DP

• 数字计数
• 数字染色
• 数字游戏

优化技巧

空间优化

1. 滚动数组
2. 状态压缩
3. 一维化处理

时间优化

1. 预处理
2. 单调队列/单调栈
3. 四边形不等式

解题技巧

状态设计

1. 考虑问题的最后一步
2. 化整为零，分解问题
3. 寻找状态表示方式

方程推导

1. 考虑所有可能的转移
2. 确保转移的完备性
3. 验证转移的正确性

边界处理

1. 初始状态的设定
2. 特殊情况的处理
3. 数组越界的预防

常见误区

1. 贪心与动态规划的混淆
2. 递归与动态规划的区别
3. 状态设计过于复杂
4. 遗漏重要状态转移

练习建议

1. 从简单问题开始
2. 多画状态转移图
3. 注重空间时间优化
4. 总结相似问题规律

复杂度分析

时间复杂度

• 由状态数量和状态转移决定
• 通常为 到
• 状态压缩可能达到

空间复杂度

• 基本为 或
• 可通过滚动数组优化
• 某些问题可降至