Appearance
动态规划
动态规划（Dynamic Programming，DP）是解决复杂问题的强大算法思想，通过将复杂问题分解为重叠子问题，并存储子问题的解来避免重复计算。
一、什么是动态规划？
1.1 生活化的理解
想象你在爬一个有100级的楼梯：
- 每次可以爬1级或2级
- 问：有多少种不同的方法爬到第100级？
如果用普通的递归，你会重复计算很多次：
- 计算到第10级的方法时，会重复计算到第8级、第9级的方法
- 动态规划的思想是：把每次计算的结果记下来，下次直接用
1.2 核心思想
动态规划的核心是：大事化小，小事化了
- 大事化小：把大问题分解成小问题
- 小事化了：把小问题的解存储起来，避免重复计算
二、动态规划的三大特征
2.1 最优子结构
定义：问题的最优解包含子问题的最优解
例子：最短路径问题
- 从北京到上海的最短路径，一定包含从北京到某个中间城市的最短路径
- 如果北京→南京→上海是最短路径，那么北京→南京也必须是北京到南京的最短路径
2.2 重叠子问题
定义：在求解过程中，许多子问题会被重复计算
例子：斐波那契数列
txt
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)可以看到F(3)被计算了两次，这就是重叠子问题
2.3 无后效性
定义：当前状态一旦确定，后续决策不会影响前面的状态
例子：买股票问题
- 第5天的决策只依赖于第4天的状态，与第1-3天的具体决策无关
三、动态规划解题五步法
步骤1：定义状态
问题：用什么变量来描述问题的状态？
技巧：
- 一维状态：dp[i]表示前i个元素的最优解
- 二维状态：dp[i][j]表示前i个元素中，容量为j时的最优解
- 三维状态：dp[i][j][k]表示前i个元素，使用j个，达到状态k的最优解
步骤2：状态转移方程
问题：如何从已知状态推导未知状态？
常见模式：
- 累加模式：dp[i] = dp[i-1] + dp[i-2]（斐波那契）
- 选择模式：dp[i] = max(dp[i-1], dp[i-2] + nums[i])（打家劫舍）
- 组合模式：dp[i][j] = dp[i-1][j] + dp[i][j-1]（路径计数）
步骤3：初始化
问题：边界条件是什么？
常见初始化：
- dp[0] = 0 或 1
- dp[0][j] = 0
- dp[i][0] = 0
步骤4：计算顺序
问题：从小到大还是从大到小？
原则：
- 确保计算dp[i]时，dp[i-1]等依赖的状态已经计算好
- 通常是从左到右、从上到下
步骤5：返回结果
问题：最终答案在哪里？
常见结果位置：
- dp[n]：前n个元素的结果
- dp[n][m]：前n个元素，容量为m的结果
- max(dp)：所有状态中的最大值
四、动态规划分类详解
4.1 线性动态规划
特征：状态是一维的，按线性顺序转移
经典问题1：爬楼梯
问题描述：每次可以爬1级或2级，求爬到第n级的方法数
生活场景：想象你在爬一个有5级的楼梯，每次可以选择迈1级或2级，问有多少种不同的方法爬到第5级？
状态定义：dp[i] = 爬到第i级台阶的方法总数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
- 从第i-1级迈1级上来 → 方法数：dp[i-1]
- 从第i-2级迈2级上来 → 方法数：dp[i-2]
初始化：
- dp[0] = 1（地面就是1种方法）
- dp[1] = 1（只有1种方法：直接迈1级）
详细计算过程：
| 级数i | 计算过程 | 结果 | 具体路径 |
|---|---|---|---|
| dp[0] | 初始化 | 1 | 起点 |
| dp[1] | 初始化 | 1 | 1 |
| dp[2] | dp[1] + dp[0] = 1 + 1 | 2 | 1→1, 2 |
| dp[3] | dp[2] + dp[1] = 2 + 1 | 3 | 1→1→1, 1→2, 2→1 |
| dp[4] | dp[3] + dp[2] = 3 + 2 | 5 | 1→1→1→1, 1→1→2, 1→2→1, 2→1→1, 2→2 |
| dp[5] | dp[4] + dp[3] = 5 + 3 | 8 | 8种完整路径 |
8种具体方法：
方法1：1→1→1→1→1（每次都迈1级）
方法2：1→1→1→2（最后迈2级）
方法3：1→1→2→1（中间迈2级）
方法4：1→2→1→1（第二个迈2级）
方法5：2→1→1→1（第一个迈2级）
方法6：1→2→2（两次迈2级）
方法7：2→1→2（中间迈1级）
方法8：2→2→1（前两次迈2级）图解：
级数： 0 1 2 3 4 5
方法数： 1 1 2 3 5 8巧妙之处：动态规划把指数级O(2^n)的递归复杂度降到线性级O(n)，通过存储中间结果避免重复计算！
经典问题2：打家劫舍
问题描述：一排房子，不能连续偷相邻的两家，求最大金额
状态定义：dp[i] = 偷到第i家时的最大金额
状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
4.2 背包动态规划
特征：在容量限制下选择物品，使价值最大化
0-1背包问题
问题描述：每个物品只能选一次
状态定义：dp[i][j] = 前i个物品，容量为j时的最大价值
状态转移：
- 不选第i个物品：dp[i][j] = dp[i-1][j]
- 选第i个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]
- 取最大值：dp[i][j] = max(上述两种情况)
完全背包问题
问题描述：每个物品可以选无限次
与0-1背包的区别：
- 0-1背包：从后往前更新（避免重复使用）
- 完全背包：从前往后更新（允许重复使用）
4.3 区间动态规划
特征：状态表示一个区间[i,j]，通过合并小区间得到大区间
经典问题：矩阵链乘法
问题描述：给定矩阵链，找出最优乘法顺序
状态定义：dp[i][j] = 计算矩阵i到j的最小乘法次数
状态转移：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])
其中k从i到j-14.4 状态压缩动态规划
特征：使用位运算来压缩状态，处理复杂约束
经典问题：旅行商问题
问题描述：访问所有城市的最短路径
状态定义：dp[mask][i] = 已经访问mask表示的城市集合，当前在i城市的最短路径
五、空间优化技巧
5.1 滚动数组优化
适用场景：当前状态只依赖于前一个或前几个状态
例子：斐波那契数列
python
# 优化前：O(n)空间
dp = [0] * (n + 1)
# 优化后：O(1)空间
prev2, prev1 = 0, 1
for i in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr5.2 降维优化
适用场景：二维DP可以降为一维
例子：0-1背包问题
python
# 优化前：二维数组
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# 优化后：一维数组
dp = [0] * (capacity + 1)5.3 对称性优化
适用场景：问题具有对称性，可以减少计算量
六、实际应用场景
6.1 金融领域
- 股票买卖：计算最大收益
- 投资组合：在风险约束下最大化收益
6.2 生物信息学
- 序列比对：DNA序列的相似性分析
- 基因预测：寻找基因编码区域
6.3 游戏开发
- AI决策：NPC的最优行动选择
- 路径规划：角色的智能移动
6.4 网络优化
- 路由算法：寻找最短路径
- 流量控制：网络包的最优传输
七、学习路径建议
7.1 新手入门（1-2周）
目标：掌握基本思想和简单问题
推荐练习：
- 爬楼梯（线性DP）
- 斐波那契数列（记忆化搜索）
- 最大子数组和（线性DP）
7.2 进阶提升（2-4周）
目标：掌握常见分类和解题技巧
推荐练习：
- 0-1背包问题（背包DP）
- 最长递增子序列（序列DP）
- 编辑距离（二维DP）
7.3 高级应用（4-8周）
目标：解决复杂问题，掌握优化技巧
推荐练习：
- 区间DP问题
- 状态压缩DP
- 树形DP
- 数位DP
八、常见误区与解决方案
8.1 误区1：状态定义不清晰
表现：不知道如何定义dp数组
解决方案：
- 先思考：用什么变量能完整描述问题的状态？
- 画表格：手动计算小例子，找出规律
- 问问题：如果已知dp[i-1]，能否推导出dp[i]？
8.2 误区2：状态转移方程错误
表现：递推关系不正确
解决方案：
- 分类讨论：考虑所有可能的选择
- 验证边界：检查边界条件是否满足
- 小例子验证：用手算验证小例子
8.3 误区3：初始化错误
表现：边界条件设置不当
解决方案：
- 理解含义：明确dp[0]代表什么
- 特殊情况：考虑空数组、空字符串的情况
- 逐步调试：打印中间结果检查
九、经典问题总结表
| 问题类型 | 经典问题 | 状态定义 | 状态转移 | 时间复杂度 |
|---|---|---|---|---|
| 线性DP | 爬楼梯 | dp[i] | dp[i]=dp[i-1]+dp[i-2] | O(n) |
| 背包DP | 0-1背包 | dp[i][j] | max选/不选 | O(n×W) |
| 序列DP | 最长递增子序列 | dp[i] | max(dp[j])+1 | O(n²) |
| 区间DP | 矩阵链乘法 | dp[i][j] | min分割点 | O(n³) |
| 编辑距离 | 字符串编辑 | dp[i][j] | min增删改 | O(m×n) |
十、实战练习建议
10.1 入门练习
- LeetCode 70：爬楼梯
- LeetCode 53：最大子数组和
- LeetCode 198：打家劫舍
10.2 进阶练习
- LeetCode 300：最长递增子序列
- LeetCode 416：分割等和子集
- LeetCode 72：编辑距离
10.3 高级练习
- LeetCode 132：分割回文串II
- LeetCode 312：戳气球
- LeetCode 10：正则表达式匹配
总结
动态规划是一种强大的算法思想，关键在于：
- 理解问题：找出最优子结构和重叠子问题
- 正确定义状态：用最少变量描述问题状态
- 建立状态转移：找出递推关系
- 注意边界条件：正确初始化
- 考虑空间优化：在需要时进行优化
记住：动态规划不是背模板，而是理解思想，灵活运用！
建议下一步：选择3-5个经典问题，从简单到复杂逐步练习，体会动态规划的思想精髓。