02.7.1 DP 基础与线性 DP
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划
这个知识域解决什么问题
动态规划的基础方法与一维、二维线性题型。本知识域按主线展开:DP 状态设计与转移 → 背包问题 → 子序列问题 → 线性 DP 进阶;每题给出「状态定义 → 转移方程 → 初始化 → 遍历顺序 → 复杂度」完整推导链。
知识地图
DP 状态设计与转移(1)
→ 背包问题(2)
→ 子序列问题(3)
→ 线性 DP 进阶(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.7.1.1 | DP 状态设计与转移 | DP 三条件、五步法、状态定义角度、最后一步反推、初始化、遍历顺序、滚动优化、爬楼梯/打家劫舍/最大子数组 | 20 |
| 02.7.1.2 | 背包问题 | 01/完全/多重背包、倒序正序、恰好装满、组合数与排列数、零钱兑换、目标和、等和子集、二进制拆分 | 20 |
| 02.7.1.3 | 子序列问题 | LIS 两种复杂度、LCS、重复子数组、编辑距离、回文子序列、不同子序列计数、单词拆分、连续与不连续区分 | 20 |
| 02.7.1.4 | 线性 DP 进阶 | 股票状态机各变体、环形/树形打家劫舍、摆动序列、三角形路径、解码、不同路径、地牢反向 DP、正则通配符匹配 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程(含状态定义与转移链) → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径。
学习路径
先 1 吃透状态设计五步法,再 2 掌握背包分类与顺序,3 练熟双序列子序列转移,最后 4 扩展到状态机与各类线性综合题。
自检
- [ ] 能按五步法写出状态定义、转移方程、初始化、遍历顺序与返回状态
- [ ] 能区分 01/完全背包并写对倒序/正序与组合/排列外层
- [ ] 能实现 LIS O(n²) 与 O(n log n),讲清 tails 含义
- [ ] 能写 LCS、编辑距离并区分连续与不连续转移
- [ ] 能搭股票持有/未持有状态机,处理冷冻期、手续费、K 次交易
- [ ] 能判断线性 DP 状态数与转移代价并报复杂度
- [ ] 每题能列出边界用例与不可达初始化口径