【动态规划 解析】

动态规划（Dynamic Programming, 简称 DP）是一种用于求解最优子结构问题的算法思想，特别适合解决有重叠子问题和最优子结构的问题，比如背包问题、最长子序列、路径规划等。

---

🌱 一、什么是动态规划？

动态规划的核心是：

“将复杂问题拆分成子问题，保存子问题的结果，避免重复计算。”

这通常通过一个数组（或字典）来记录中间结果，逐步构建最终解。

• 重叠子问题：子问题会重复出现。
• 最优子结构：问题的最优解包含子问题的最优解。

---

🧠 二、写动态规划题的 5 个标准步骤

记住这个套路模板：确定状态 → 状态转移方程 → 初始化 → 遍历顺序 → 输出结果

---

🧩 1. 确定「状态」

• 也就是定义 dp[i] 的含义，表示什么含义？

例：dp[i] 表示前 i 项的最大价值，或者第 i 个位置结尾的最长子序列等等。

---

🔁 2. 写「状态转移方程」

这就是核心推理过程，从小规模问题一步步构建大问题的解。

• 常见形式如：

  dp[i] = max(dp[i-1], dp[i-2] + value[i])
  

---

🔢 3. 初始化「边界条件」

给 dp 数组设置初始值，很多题在 dp[0]、dp[1] 要手动指定。

---

🔄 4. 选择「遍历顺序」

• 递推是从小到大
• 有时要从后往前（如 01 背包）

---

✅ 5. 输出「最终结果」

有些题的结果是 dp[n]，有些是 max(dp)，要结合题目理解。

---

🧱 三、代码模板（以“打家劫舍”为例）

题目：不能偷相邻的房子，每个房子有金额，求最大收益。

def rob(nums):if not nums:return 0n = len(nums)if n == 1:  # 边界return nums[0]dp = [0] * n  # dp[i] 表示偷前 i 个房子的最大收益dp[0] = nums[0]dp[1] = max(nums[0], nums[1])  # 只能偷第一个或第二个for i in range(2, n):# 偷当前这个房子 + dp[i-2]，或者不偷这个房子（用 dp[i-1]）dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[-1]

---

💡 四、动态规划的题型模板

题型	状态定义举例	转移公式举例
斐波那契数列	dp[i] 第i个数	dp[i] = dp[i-1] + dp[i-2]
背包问题	dp[i][j] 前i个物品容量j	dp[i][j] = max(...)
最长子序列/子串	dp[i][j] 以i,j结尾	dp[i][j] = ... 根据字符是否匹配
区间问题	dp[i][j] 从i到j区间	枚举中间点 k, dp[i][j] = min(...)

---

📌 五、小技巧

• 如果空间能压缩（比如只和前一项有关），就用一维 dp
• 遇到“最小值”、“最大值”、“个数”之类关键词，考虑 DP
• 写不出转移方程？用样例推几步观察规律！

---

🎯 总结口诀

DP五部曲口诀：

1. 定义状态最关键；
2. 转移方程要看清；
3. 初始化边界定；
4. 遍历顺序别写错；
5. 输出结果莫粗心。