罗罗编程学习记录
本页内容 展开查看

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 状态数与转移代价并报复杂度
  • [ ] 每题能列出边界用例与不可达初始化口径