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

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 为主;每题给出状态定义、转移方程、初始化、遍历顺序与复杂度口径。