动态规划（DP）系统分类与经典题型详解

动态规划（Dynamic Programming, DP） 是算法中解决最优化问题的核心方法之一。其核心思想是将原问题分解为多个重叠子问题，并通过记忆化存储避免重复计算。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

一、动态规划四大关键要素

1. 状态定义：明确 dp[i] 或 dp[i][j] 的含义

   示例：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度

2. 状态转移方程：找到子问题之间的关系

   示例：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

3. 初始化：设定边界条件

   示例：dp[0] = 1

4. 遍历顺序：根据依赖关系确定顺序

   示例：一维DP常从左到右，二维DP需双重循环

---

二、动态规划经典题型分类

1. 线性DP（一维/二维）

（1）基础问题

🧱 70. 爬楼梯

• 状态定义：dp[i] 表示爬到第 i 阶的方法数
• 转移方程：dp[i] = dp[i-1] + dp[i-2]
• 初始化：dp[0] = 1, dp[1] = 1

💰 198. 打家劫舍

• 状态定义：dp[i] 表示偷到第 i 家的最大金额
• 转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

（2）序列问题

📈 300. 最长递增子序列 (LIS)

• 状态定义：dp[i] 表示以 nums[i] 结尾的 LIS 长度
• 转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]
• 优化：可结合二分查找将时间复杂度从 $O(n^2)$ 降到 $O(n \log n)$

🔢 53. 最大子数组和

• 状态定义：dp[i] 表示以 nums[i] 结尾的最大子数组和
• 转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])

---

2. 背包问题

（1）0-1背包

🎒 416. 分割等和子集

• 状态定义：dp[i][j] 表示前 i 个物品能否凑出重量 j
• 转移方程：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
• 空间优化：使用一维数组倒序遍历

➕ 494. 目标和

• 转化思路：转化为子集和为 (target + sum(nums)) / 2 的背包问题

（2）完全背包

💸 322. 零钱兑换

• 状态定义：dp[i] 表示凑出金额 i 的最小硬币数
• 转移方程：dp[i] = min(dp[i], dp[i-coin] + 1)
• 遍历顺序：外层金额，内层硬币（完全背包特点）

---

3. 区间DP

🔁 5. 最长回文子串

• 状态定义：dp[i][j] 表示子串 s[i..j] 是否为回文
• 转移方程：dp[i][j] = (s[i] == s[j]) && (j-i <= 2 || dp[i+1][j-1])
• 遍历顺序：按子串长度从小到大

🎈 312. 戳气球

• 状态定义：dp[i][j] 表示戳破区间 (i,j) 内气球的最大得分
• 转移方程：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])

---

4. 树形DP

🏡 337. 打家劫舍 III

• 状态定义：dp[node][0/1] 表示偷/不偷当前节点的最大金额
• 转移方程：
  • 偷当前节点：dp[node][1] = val + dp[left][0] + dp[right][0]
  • 不偷当前节点：dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])

---

5. 状态机DP

📉 122. 买卖股票的最佳时机 II

• 状态定义：
  • dp[i][0]：第 i 天不持有股票的最大利润
  • dp[i][1]：第 i 天持有股票的最大利润
• 转移方程：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

---

三、动态规划解题技巧总结

1. ✍️ 画状态转移表：用表格帮助理解状态转移过程（如二维DP填表法）
2. 🔁 从暴力递归入手：先写递归再改记忆化搜索
3. 🚀 空间优化技巧：滚动数组、只保留前一行等
4. 🧪 打印DP表调试：验证逻辑是否正确

---

四、高频动态规划题目列表

类型	经典题目
线性DP	70. 爬楼梯、198. 打家劫舍
序列问题	300. LIS、1143. LCS
背包问题	416. 分割等和子集、322. 零钱兑换
区间DP	5. 最长回文子串、312. 戳气球
树形DP	337. 打家劫舍 III
状态机DP	121. 买卖股票 I、309. 含冷冻期

---

五、总结与建议

动态规划的本质是“用空间换时间”，通过拆解问题、记录中间结果来避免重复计算。

掌握路径建议：

1. 多刷经典题型：每类至少完成3~5题，熟悉典型状态转移方式
2. 从简单题开始：逐步建立对状态定义的直觉
3. 理解问题背景：例如背包问题中的“选择”与“约束”
4. 对比分析差异：不同题目状态转移方程的异同有助于加深理解

---

📌 推荐练习顺序：线性DP → 序列问题 → 背包问题 → 区间DP → 树形DP → 状态机DP