动态规划
学完这一节，你应该能够
从状态定义、转移来源和遍历顺序出发，依次掌握线性、序列、背包、网格、区间、树形、状态压缩与数位动态规划。
前置知识
- 算法基础与问题建模
- 递归、搜索与回溯
- 树
解题框架
- 动态规划基础与线性状态
- 序列与字符串动态规划
- 背包模型
- 网格与路径动态规划
- 区间动态规划
- 树形动态规划
- 状态压缩动态规划
- 数位动态规划
母题路线
| 层级 | 解题框架 | 题目 | 站内题解 |
|---|---|---|---|
| 必学 | 动态规划基础与线性状态 | LeetCode 70. 爬楼梯 | 阅读题解 |
| 必学 | 动态规划基础与线性状态 | LeetCode 53. 最大子数组和 | 阅读题解 |
| 必学 | 动态规划基础与线性状态 | LeetCode 198. 打家劫舍 | 阅读题解 |
| 必学 | 动态规划基础与线性状态 | LeetCode 152. 乘积最大子数组 | 阅读题解 |
| 必学 | 序列与字符串动态规划 | LeetCode 300. 最长递增子序列 | 阅读题解 |
| 必学 | 序列与字符串动态规划 | LeetCode 139. 单词拆分 | 阅读题解 |
| 必学 | 序列与字符串动态规划 | LeetCode 1143. 最长公共子序列 | 阅读题解 |
| 必学 | 序列与字符串动态规划 | LeetCode 72. 编辑距离 | 阅读题解 |
| 必学 | 序列与字符串动态规划 | LeetCode 32. 最长有效括号 | 阅读题解 |
| 拓展 | 序列与字符串动态规划 | LeetCode 115. 不同的子序列 | 阅读题解 |
| 必学 | 背包模型 | AcWing 2. 01 背包问题 | 阅读题解 |
| 必学 | 背包模型 | AcWing 3. 完全背包问题 | 阅读题解 |
| 必学 | 背包模型 | LeetCode 416. 分割等和子集 | 阅读题解 |
| 必学 | 背包模型 | LeetCode 322. 零钱兑换 | 阅读题解 |
| 必学 | 背包模型 | LeetCode 518. 零钱兑换 II | 阅读题解 |
| 拓展 | 背包模型 | AcWing 4. 多重背包问题 I | 阅读题解 |
| 必学 | 网格与路径动态规划 | LeetCode 62. 不同路径 | 阅读题解 |
| 必学 | 网格与路径动态规划 | LeetCode 64. 最小路径和 | 阅读题解 |
| 必学 | 网格与路径动态规划 | AcWing 898. 数字三角形 | 阅读题解 |
| 必学 | 网格与路径动态规划 | LeetCode 221. 最大正方形 | 阅读题解 |
| 必学 | 区间动态规划 | LeetCode 5. 最长回文子串 | 阅读题解 |
| 必学 | 区间动态规划 | AcWing 282. 石子合并 | 阅读题解 |
| 拓展 | 区间动态规划 | LeetCode 312. 戳气球 | 阅读题解 |
| 必学 | 树形动态规划 | LeetCode 337. 打家劫舍 III | 阅读题解 |
| 拓展 | 树形动态规划 | LeetCode 968. 监控二叉树 | 阅读题解 |
| 拓展 | 树形动态规划 | LeetCode 834. 树中距离之和 | 阅读题解 |
| 拓展 | 状态压缩动态规划 | AcWing 91. 最短 Hamilton 路径 | 阅读题解 |
| 拓展 | 状态压缩动态规划 | AcWing 291. 蒙德里安的梦想 | 阅读题解 |
| 拓展 | 数位动态规划 | AcWing 1081. 度的数量 | 阅读题解 |
| 拓展 | 数位动态规划 | LeetCode 2376. 统计特殊整数 | 阅读题解 |
下一章： 数学