$$\color{Red}{【算法题】《动态规划》复习笔记}$$
我的网站=> 分享了我关于前后端的各种知识和生活美食~
我于Acwing平台分享的零散刷的各种各样的题
一.分类题单
每道题都有我写的解析，如果发现有不对的地方欢迎各位大佬指正
1.背包问题
1.1 01背包模型
| 题目 | 总结归纳 |
|---|---|
1. 01背包问题 (1.二维状态表示 2. 一维状态优化) |
习题总结 |
2. 采药 板子题 |
习题总结 |
| 3. 装箱问题 | 习题总结 |
| 4. 二维费用背包问题 | 习题总结 |
5. 宠物小精灵之收服 二维费用背包问题 |
习题总结 |
6. 潜水员 二维最小值背包 推广新状态 |
习题总结 |
| 7. 数字组合 | 习题总结 |
8. 背包问题求具体方案 01背包求方案数 |
习题总结 |
| 9. | 习题总结 |
1.2 完全背包模型
| 题目 | 总结归纳 |
|---|---|
1. 完全背包问题 (1.二维状态表示 2.一维状态优化) |
习题总结 |
2. 买书 完全背包求方案数 |
习题总结 |
3. 货币系统 完全背包求方案数 |
习题总结 |
4. 货币系统 完全背包方案求极大无关组 |
习题总结 |
5. 正则匹配字符串 leetcode10 正则DP |
习题总结 |
| 6. | 习题总结 |
| 7. | 习题总结 |
| 8. | 习题总结 |
1.3 多重背包模型
| 题目 | 总结归纳 |
|---|---|
1. 多重背包问题朴素版 (1类似完全背包 2.强行拆01背包) |
习题总结 |
2. 多重背包问题plus(二进制划分01背包) |
习题总结 |
3. 庆功会 模板题 |
习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
1.4 分组背包模型
| 题目 | 总结归纳 |
|---|---|
1. 分组背包问题(1.二维状态表示 2. 一维状态优化) |
习题总结 |
2. 机器分配 求方案数+分组背包 |
习题总结 |
3. 金明的预算方案 有依赖的分组背包（二进制选取） |
习题总结 |
| 4. | 习题总结 |
| 5. | 习题总结 |
1.5 混合背包模型
| 题目 | 总结归纳 |
|---|---|
1. 混合背包问题 1 转化为多重背包 2 混合背包模型 |
习题总结 |
| 2. | 习题总结 |
| 3. | 习题总结 |
1.6 背包模型综合题
| 题目 | 总结归纳 |
|---|---|
1. 有依赖的背包问题 没有上司的舞会 + 金明的预算方案 |
习题总结 |
2. 能量石 贪心推公式 + 01背包 |
习题总结 |
| 3. | 习题总结 |
2.线性DP
2.1 数字三角形模型
| 题目 | 总结归纳 |
|---|---|
1. 数字三角形（1.从上到下 2.从下到上） |
习题总结 |
| 2. 摘花生 | 习题总结 |
| 3. 最低通行费 | 习题总结 |
4. 方格取数 两条路径的三角形模型 |
习题总结 |
5. 传纸条 方格取数完全相同思路 |
习题总结 |
6. 不同路径 leetcode 62 摘花生求方案数 |
习题总结 |
7. 不同路径2 leetcode 63 有障碍版 |
习题总结 |
8. 最小路径和 leetcode 64 摘花生模板 |
习题总结 |
9. 交错字符串 leetcode 97 线性dp |
习题总结 |
| 10. | 习题总结 |
| 11. | 习题总结 |
| 12. | 习题总结 |
| 13. | 习题总结 |
| 14. | 习题总结 |
| 15. | 习题总结 |
| 16. | 习题总结 |
| 17. | 习题总结 |
2.2 最长上升子序列模型
| 题目 | 总结归纳 |
|---|---|
1. 最长上升子序列 (基础DP) |
同下 |
2. 最长上升子序列 (优化版) |
习题总结 |
3. 怪盗基德的滑翔翼 (双向选其一) |
习题总结 |
4. 登山 （双向组合） |
习题总结 |
5. 合唱队形 登山对偶问题 |
习题总结 |
6. 友好城市 组合排序类 |
习题总结 |
| 7. 最大上升子序列和 | 习题总结 |
8. 拦截导弹 结合贪心思路 |
习题总结 |
9. 导弹防御系统 贪心结合DFS升级 |
习题总结 |
| 10. | 习题总结 |
| 11. | 习题总结 |
| 3. | 习题总结 |
2.2 其他线性模型
| 题目 | 总结归纳 |
|---|---|
1. 最长不连续公共子序列 (和kmp要区分开) |
习题总结 |
2. 最短编辑距离 (完全匹配的规划) |
习题总结 |
| 3. 编辑距离 | 习题总结 |
4. 地宫取宝 摘花生+上升子序列 |
习题总结 |
5. 最大连续子数组和 leetcode 53 最大连续和 |
习题总结 |
6. 不同的子序列 leetcode 115 线性dp |
习题总结 |
| 7. | 习题总结 |
| 8. | 习题总结 |
| 9. | 习题总结 |
| 10. | 习题总结 |
| 11. | 习题总结 |
| 12. | 习题总结 |
| 13. | 习题总结 |
| 14. | 习题总结 |
| 15. | 习题总结 |
| 16. | 习题总结 |
| 17. | 习题总结 |
3.区间DP
| 题目 | 总结归纳 |
|---|---|
1. 石子合并 （理解区间DP的模板) |
习题总结 |
2. 环形石子合并 把环形问题转化为链形 |
习题总结 |
3. 能量项链 二维的石子，相邻的区间 |
习题总结 |
4. 凸多边形的划分 能量项链——>高精度 |
习题总结 |
5. 加分二叉树 区间为空的特判&二叉树遍历的性质 |
习题总结 |
| 6. | 习题总结 |
4.计数类DP
| 题目 | 总结归纳 |
|---|---|
1. 整数划分 （理解计数DP的属性) |
习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
5.数位统计DP
| 题目 | 总结归纳 |
|---|---|
| 1. | |
| 3. | 习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
6.状态压缩DP
| 题目 | 总结归纳 |
|---|---|
1. 蒙德里安的梦想 （理解状态压缩DP的基本原理) |
习题总结 |
2. 最短哈密顿距离 （位运算在状态变化的使用！） |
习题总结 |
3. 小国王 蒙德里安plus 棋盘状压DP |
习题总结 |
4. 玉米田 小国王无数量限制版 |
习题总结 |
5. 炮兵阵地 玉米田升级维度版 |
习题总结 |
5. 愤怒的小鸟 融合数学知识的状压DP |
习题总结 |
| 5. | 习题总结 |
| 5. | 习题总结 |
7.树形DP
| 题目 | 总结归纳 |
|---|---|
1. 没有上司的舞会 （帮助理解树的重心) |
习题总结 |
| 2. 树的最长路径 | 习题总结 |
3. 树的中心 两次不同的dfs 次长保证换点 |
习题总结 |
4. 数字转换 融合筛约数的树形dp |
习题总结 |
5. 二叉苹果树 有依赖的背包问题边型版 |
习题总结 |
6. 有依赖的背包问题 没有上司的舞会 + 金明的预算方案 |
习题总结 |
7. 战略游戏 极小点覆盖 |
习题总结 |
8. 皇宫看守 极小边覆盖 |
习题总结 |
9. 树的重心 树的深度优先遍历——深入理解递归 |
习题总结 |
10. 二叉树中的最大路径和 leetcode124 树形dp |
习题总结 |
| 11. | 习题总结 |
| 12. | 习题总结 |
| 13. | 习题总结 |
| 14. | 习题总结 |
| 15. | 习题总结 |
| 16. | 习题总结 |
| 17. | 习题总结 |
| 18. | 习题总结 |
| 19. | 习题总结 |
| 20. | 习题总结 |
| ---------- |
8.记忆化搜索
| 题目 | 总结归纳 |
|---|---|
| 1. 滑雪 | 习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
| 3. | 习题总结 |
9.状态机模型
| 题目 | 总结归纳 |
|---|---|
| 1. 大盗阿福 | 习题总结 |
| 2. 股票问题IV | 习题总结 |
3. 股票买卖V 带冷却天数的状态机 |
习题总结 |
| 3. | 习题总结 |
10.单调队列优化
| 题目 | 总结归纳 |
|---|---|
| 1. 最大子序和【单调队列优化DP】 | 习题总结 |
| 2. 修剪草坪 | 习题总结 |
| 3. 烽火传递 | 习题总结 |
4. 绿色通道 烽火传递二分plus |
习题总结 |
| 5. | 习题总结 |
| 6. | 习题总结 |
$6$