02.7 动态规划
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- DP 三条件、五步法、状态定义角度、最后一步反推、初始化、遍历顺序、滚动优化
- 01/完全/多重背包、倒序正序、恰好装满、组合数与排列数、零钱兑换、目标和、等和子集
- LIS 两种复杂度、LCS、重复子数组、编辑距离、回文子序列、子序列计数、单词拆分
- 股票状态机各变体、环形/树形打家劫舍、摆动序列、三角形路径、解码、不同路径、正则匹配
- 区间 DP:长度外层、分割点、石子合并、戳气球、矩阵链乘、回文区间、博弈区间
- 树形 DP:后序两状态、最大路径和、打家劫舍 III、直径、独立集/点覆盖、树上背包
- 状态压缩:掩码位运算、TSP、Hamilton 路径、行型放置、2ⁿ 规模估算
- 数位 DP:tight/leading、前缀差分、数位和与相邻约束;概率/期望/博弈 DP 变体
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.7.1 | DP 基础与线性 DP | 4 个子主题 80 题:DP 状态设计与转移、背包问题、子序列问题、线性 DP 进阶 |
| 02.7.2 | 区间树形与状态压缩 DP | 4 个子主题 80 题:区间 DP、树形 DP、状态压缩 DP、数位 DP 与其他 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.7.1.1-014 | 爬楼梯(LC 70) | 简单 | ★★★★★ | DP 状态设计与转移 |
| 02.7.1.1-015 | 打家劫舍(LC 198) | 中等 | ★★★★★ | DP 状态设计与转移 |
| 02.7.1.1-016 | 最大子数组和(LC 53) | 中等 | ★★★★★ | DP 状态设计与转移 |
| 02.7.1.1-017 | 乘积最大子数组(LC 152) | 中等 | ★★★★☆ | DP 状态设计与转移 |
| 02.7.1.2-007 | 零钱兑换 I(LC 322) | 中等 | ★★★★★ | 背包问题 |
| 02.7.1.2-008 | 零钱兑换 II(LC 518) | 中等 | ★★★★☆ | 背包问题 |
| 02.7.1.2-009 | 目标和(LC 494) | 中等 | ★★★★☆ | 背包问题 |
| 02.7.1.2-010 | 分割等和子集(LC 416) | 中等 | ★★★★☆ | 背包问题 |
| 02.7.1.3-002 | 最长递增子序列(LC 300) | 中等 | ★★★★★ | 子序列问题 |
| 02.7.1.3-005 | 最长公共子序列(LC 1143) | 中等 | ★★★★★ | 子序列问题 |
| 02.7.1.3-007 | 编辑距离(LC 72) | 困难 | ★★★★☆ | 子序列问题 |
| 02.7.1.3-017 | 最长回文子序列(LC 516) | 中等 | ★★★★☆ | 子序列问题 |
| 02.7.1.4-001 | 股票 I 一次交易(LC 121) | 简单 | ★★★★★ | 线性 DP 进阶 |
| 02.7.1.4-003 | 股票 III 最多两次(LC 123) | 困难 | ★★★★☆ | 线性 DP 进阶 |
| 02.7.1.4-008 | 打家劫舍 II 环形(LC 213) | 中等 | ★★★★☆ | 线性 DP 进阶 |
| 02.7.1.4-015 | 最小路径和(LC 64) | 中等 | ★★★★☆ | 线性 DP 进阶 |
| 02.7.1.4-017 | 正则匹配(LC 10) | 困难 | ★★★☆☆ | 线性 DP 进阶 |
| 02.7.2.1-004 | 石子合并 | 困难 | ★★★★☆ | 区间 DP |
| 02.7.2.1-005 | 戳气球(LC 312) | 困难 | ★★★★☆ | 区间 DP |
| 02.7.2.1-007 | 最长回文子串(LC 5) | 中等 | ★★★★★ | 区间 DP |
| 02.7.2.1-009 | 预测赢家(LC 486) | 中等 | ★★★☆☆ | 区间 DP |
| 02.7.2.2-003 | 二叉树最大路径和(LC 124) | 困难 | ★★★★★ | 树形 DP |
| 02.7.2.2-004 | 打家劫舍 III(LC 337) | 中等 | ★★★★☆ | 树形 DP |
| 02.7.2.2-005 | 二叉树直径(LC 543) | 简单 | ★★★★☆ | 树形 DP |
| 02.7.2.3-005 | TSP 旅行商 | 困难 | ★★★☆☆ | 状态压缩 DP |
| 02.7.2.3-007 | 相邻不冲突放置状压 | 困难 | ★★★☆☆ | 状态压缩 DP |
| 02.7.2.4-004 | 不含连续 1 的数字 | 困难 | ★★★☆☆ | 数位 DP 与其他 |
| 02.7.2.4-005 | 各位数字之和计数 | 中等 | ★★★☆☆ | 数位 DP 与其他 |
| 02.7.2.4-011 | 博弈胜负态与 Nim 概念 | 中等 | ★★★☆☆ | 数位 DP 与其他 |
当前状态
- 02.7.1 已完成 4 个子主题、80 题;02.7.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;每题给出状态定义、转移方程、初始化、遍历顺序与复杂度口径。