动态规划综合通关：高频模式识别与面试决策树

摘要

经过前九篇的系统学习，你已经掌握了从基础到高级的七大 DP 类型：线性 DP、背包 DP、子序列 DP、矩阵路径 DP、区间 DP、字符串 DP、树形与状态压缩 DP。本文是全系列的综合收官篇，聚焦两个核心目标：一是系统梳理高频面试 DP 模式，给出快速识别线索；二是深度讲解买卖股票系列（LeetCode 121/122/123/188/309）——这是一个以”状态机 DP”为核心的完整题系，代表了 DP 在多约束、多维状态问题上的最高水平。

第 1 章 DP 模式的快速识别

1.1 面试中识别 DP 问题的四个信号

信号一：求最优值（最大/最小）。题目要求求某个最大值、最小值、最短路径、最少操作数……绝大多数情况下是 DP（或贪心，但贪心需要更强的证明）。

信号二：求计数（有多少种方案）。题目问”有多少种方法/路径/子序列”，通常是 DP（将”取最优”改为”求和”）。

信号三：输入是序列/矩阵/树。对于这类结构化输入，每个”位置”的决策影响后续决策，子问题重叠，DP 是首选。

信号四：最优子结构存在。如果能把问题分解为”解决子问题后，通过有限步骤得到原问题的解”，即最优子结构成立。

1.2 七大 DP 模式速查表

模式	识别关键词	典型题	核心公式形式
线性 DP	序列，选或不选	House Robber, Jump Game	`dp[i] = f(dp[i-1], dp[i-2])`
背包 DP	容量，价值，物品选择	Coin Change, 0/1 Knapsack	`dp[j] = f(dp[j], dp[j-w])`
子序列 DP	LIS, LCS, 子序列操作	LIS, Edit Distance	`dp[i] = max(dp[j]+1)` 或双序列
矩阵路径 DP	网格，路径，计数/最优	Unique Paths, Min Path Sum	`dp[i][j] = f(dp[i-1][j], dp[i][j-1])`
区间 DP	合并，分割，枚举分割点	Burst Balloons, 矩阵链乘	`dp[i][j] = min(dp[i][k]+dp[k+1][j])`
字符串 DP	回文，正则匹配，双字符串	LCS, Regex Match	双序列 + 分情况讨论
树形/状压 DP	树结构/集合状态	Tree Robber, TSP	DFS后序 / bitmask

1.3 从题目关键词快速定位 DP 类型

题目包含...         → 考虑...
"连续子数组/子串"    → 线性 DP（以 i 结尾）或滑动窗口
"不连续子序列"       → 子序列 DP（LIS/LCS 类）
"是否可达/方案数"    → 计数型 DP（通常初始化为 0，转移求和）
"最小分割/最小操作"  → 线性 DP + 区间预处理
"字符串匹配"        → 双序列 DP（s 的前 i 个 vs p 的前 j 个）
"网格/矩阵路径"      → 二维 DP（从左上到右下）
"合并区间"          → 区间 DP（枚举分割点）
"树上选择"          → 树形 DP（DFS 后序）
"集合选择/覆盖"      → 状态压缩 DP
"多次交易/有限状态"  → 状态机 DP（状态维度扩展）

第 2 章状态机 DP：买卖股票系列

2.1 什么是状态机 DP

状态机 DP 是 DP 中状态设计最精妙的变体之一。它将问题建模为一个有限状态自动机：每个时刻系统处于某个状态，每次决策导致状态转移，目标是在所有可能的决策序列中找到最优路径。

买卖股票系列是状态机 DP 的标志性题型：

系统状态：持有股票 / 不持有股票（可能还有交易次数限制）
决策：买入 / 卖出 / 持有不动
目标：最大化总利润

2.2 LeetCode 121：只允许一次交易

LeetCode 121 - Best Time to Buy and Sell Stock（简单）

只能买卖一次，求最大利润。

贪心解法（ $O (n)$ 时间 $O (1)$ 空间）：

维护历史最低价格 minPrice，遍历时更新 maxProfit = max(maxProfit, price - minPrice)。

DP 视角（为后续多次交易打下框架）：

dp[i][0]：第 i 天不持有股票的最大利润
dp[i][1]：第 i 天持有股票的最大利润

转移：

$d p [i] [0] = max (d p [i - 1] [0], d p [i - 1] [1] + price [i]) （继续不持有，或今天卖出）$

$d p [i] [1] = max (d p [i - 1] [1], - price [i]) （继续持有，或今天买入 —— 只能买一次所以买入代价是 -price[i] ）$

注意：只允许一次交易，所以买入的”初始资金”是 0，dp[i][1] 的初始化 -price[i] 代表”今天第一次买入”（没有任何历史利润）。

2.3 LeetCode 122：允许无限次交易

LeetCode 122 - Best Time to Buy and Sell Stock II（中等）

可以无限次买卖（但同一时刻只能持有一支股票），求最大利润。

贪心：只要明天比今天涨，就今天买明天卖（利润叠加）。

DP 视角：

$d p [i] [1] = max (d p [i - 1] [1], d p [i - 1] [0] - price [i])$

与 LeetCode 121 的唯一区别：dp[i][1] 的买入代价从 -price[i] 变为 dp[i-1][0] - price[i]（利用了历史利润）。

2.4 LeetCode 309：含冷冻期

LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown（中等）

卖出后有一天冷冻期，不能买入。

三状态建模：

状态 0：不持有股票，且昨天不是卖出操作（冷冻期已过，可以买入）
状态 1：持有股票
状态 2：不持有股票，且今天刚卖出（明天是冷冻期）

状态0 → 状态1（买入）
状态0 → 状态0（休息）
状态1 → 状态2（卖出）
状态1 → 状态1（继续持有）
状态2 → 状态0（冷冻期结束）

转移方程：

$d p [i] [0] = max (d p [i - 1] [0], d p [i - 1] [2])$ $d p [i] [1] = max (d p [i - 1] [1], d p [i - 1] [0] - price [i])$ $d p [i] [2] = d p [i - 1] [1] + price [i]$

答案：max(dp[n-1][0], dp[n-1][2])（不持有股票的最大利润）

public int maxProfit(int[] prices) {
    int n = prices.length;
    // dp[0]: 不持有且不在冷冻期
    // dp[1]: 持有
    // dp[2]: 刚卖出（今天是冷冻期）
    int[] dp = new int[]{0, -prices[0], Integer.MIN_VALUE};
 
    for (int i = 1; i < n; i++) {
        int newDp0 = Math.max(dp[0], dp[2]);           // 休息或从冷冻期恢复
        int newDp1 = Math.max(dp[1], dp[0] - prices[i]); // 继续持有或买入
        int newDp2 = dp[1] + prices[i];                 // 今天卖出
 
        dp[0] = newDp0;
        dp[1] = newDp1;
        dp[2] = newDp2;
    }
    return Math.max(dp[0], dp[2]);
}

2.5 LeetCode 714：含手续费

LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee（中等）

每次卖出需要支付手续费 fee。

只需在卖出时减去手续费：

$d p [i] [2] = d p [i - 1] [1] + price [i] - fee$

或在买入时：

$d p [i] [1] = max (d p [i - 1] [1], d p [i - 1] [0] - price [i] - fee)$

两种等价，只在买入或卖出时扣除一次手续费即可。

2.6 LeetCode 123：最多两次交易

LeetCode 123 - Best Time to Buy and Sell Stock III（困难）

最多完成两笔交易。

增加交易次数维度：dp[i][k][j]，k 表示还剩几次可用交易，j = 0/1 表示是否持有。

由于最多 2 次交易，状态可以展开（不用循环）：

public int maxProfit(int[] prices) {
    // buy1: 第一次买入后的最大利润（负数，代表花了钱）
    // sell1: 第一次卖出后的最大利润
    // buy2: 第二次买入后的最大利润
    // sell2: 第二次卖出后的最大利润
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
 
    for (int price : prices) {
        buy1  = Math.max(buy1,  -price);            // 第一次买入（初始资金 0）
        sell1 = Math.max(sell1, buy1 + price);      // 第一次卖出
        buy2  = Math.max(buy2,  sell1 - price);     // 第二次买入（利用第一次利润）
        sell2 = Math.max(sell2, buy2 + price);      // 第二次卖出
    }
    return sell2;
}

直觉：buy1 → sell1 → buy2 → sell2 四个状态串联，每次更新都依赖前一个状态，形成状态链。注意每次更新使用的是当天的 price，且更新顺序是从前到后（保证每个状态的”前置状态”已是最新值）。

2.7 LeetCode 188：最多 k 次交易

LeetCode 188 - Best Time to Buy and Sell Stock IV（困难）

最多完成 k 笔 交易。

通用状态机 DP：

dp[j][0]：进行了 j 次交易且不持有股票的最大利润 dp[j][1]：进行了 j 次（最后一次尚未完成）且持有股票的最大利润

转移（每天更新）：

$d p [j] [0] = max (d p [j] [0], d p [j] [1] + price)$ $d p [j] [1] = max (d p [j] [1], d p [j - 1] [0] - price)$

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    // 优化：如果 k >= n/2，等同于无限次交易（贪心）
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        }
        return profit;
    }
 
    // dp[j][0]: 完成了 j 次交易，不持有股票
    // dp[j][1]: 进行中第 j 次交易（已买入），持有股票
    int[][] dp = new int[k + 1][2];
    for (int j = 0; j <= k; j++) dp[j][1] = Integer.MIN_VALUE;  // 持有状态初始化为 -INF
 
    for (int price : prices) {
        for (int j = k; j >= 1; j--) {  // 逆序，防止同天同次操作
            dp[j][0] = Math.max(dp[j][0], dp[j][1] + price);      // 卖出
            dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - price);  // 买入（使用上一次完成的利润）
        }
    }
    return dp[k][0];
}

2.8 买卖股票系列总结

题目	约束	核心变化
LeetCode 121	最多 1 次	买入代价固定为 `-price[i]`
LeetCode 122	无限次	买入代价为 `dp[0] - price[i]`（携带历史利润）
LeetCode 309	无限次 + 冷冻期	三状态，`状态2 → 状态0`（冷冻期恢复）
LeetCode 714	无限次 + 手续费	卖出时扣减 `fee`
LeetCode 123	最多 2 次	展开四状态链 `buy1→sell1→buy2→sell2`
LeetCode 188	最多 k 次	交易次数作为 DP 维度，逆序更新

第 3 章常见陷阱与调试技巧

3.1 初始化错误

陷阱：求最小值时忘了把初始值设为 Integer.MAX_VALUE，导致错误地被 0 覆盖。

// ❌ 错误：初始值是 0，最小值会被更新为 0
int[] dp = new int[n + 1]; // 默认全 0
 
// ✅ 正确：初始值设为 MAX_VALUE
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // 只有 base case 有意义

陷阱：完全背包的 dp[0] = 0（空容量代价为 0），但 0-1 背包某些变体（如”恰好装满”）需要 dp[0] = 0，其他 dp[j] = Integer.MAX_VALUE（不可达），两者含义不同。

3.2 遍历顺序错误

0-1 背包 vs 完全背包的遍历方向：

// 0-1 背包：逆序遍历容量（防止同一物品被选多次）
for (int j = W; j >= w; j--) {
    dp[j] = Math.max(dp[j], dp[j - w] + v);
}
 
// 完全背包：正序遍历容量（允许同一物品被选多次）
for (int j = w; j <= W; j++) {
    dp[j] = Math.max(dp[j], dp[j - w] + v);
}

区间 DP 的区间长度优先：

// ❌ 错误：按起点遍历，dp[i+1][j] 可能还没算
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) { ... }
}
 
// ✅ 正确：按区间长度遍历
for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) { ... }
}

3.3 状态定义模糊

陷阱：“包含”vs”结尾是”vs”考虑到”三种状态定义混淆：

状态定义	使用场景	答案位置
`dp[i]` = 考虑前 `i` 个，结果最优	打家劫舍	`dp[n]`
`dp[i]` = 以第 `i` 个结尾，结果最优	LIS	`max(dp[i])`
`dp[i][j]` = 区间 `[i, j]` 的最优	区间 DP	`dp[0][n-1]`

“以第 i 个结尾”的状态定义答案不在末尾，需要对所有 dp[i] 取最大值。这是 LIS 类题目最常见的错误——直接返回 dp[n-1] 而不是 max(dp)。

3.4 整数溢出

在计数型 DP 中，方案数可能很大。题目通常要求取模（% 1000000007），但转移时要注意：

// ❌ 溢出：两个大数相加后取模
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;  // 如果 dp[i-1] 和 dp[i-2] 已经是 MOD 以内，这是对的
 
// ❌ 更常见的溢出场景：乘法
// dp[i] = dp[i-1] * dp[i-2]  -- 直接溢出
dp[i] = (long) dp[i-1] * dp[i-2] % MOD;  // ✅ 先转 long 再取模

第 4 章 DP 优化专题

4.1 滚动数组优化

二维 DP dp[i][j] 只依赖 dp[i-1][*]，可以用两行滚动：

// 用 curr 和 prev 两行交替使用，或用 i % 2 取模
int[][] dp = new int[2][n];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        dp[i % 2][j] = dp[(i - 1) % 2][j] + ...;
    }
}

或者压缩成一维数组（需注意更新顺序，参考背包章节）。

4.2 单调队列优化滑动窗口 DP

当 DP 转移形如 dp[i] = max(dp[j]) + cost(i)，其中 j 的范围是 [i-k, i-1]（固定窗口），可以用单调队列将 $O (nk)$ 优化为 $O (n)$ 。

例：LeetCode 239 - Sliding Window Maximum 本身不是 DP，但滑动窗口内的最大值维护技巧与单调队列优化 DP 完全一样。

例：LeetCode 1696 - Jump Game VI

从位置 i 可以跳到 [i+1, i+k] 的任意位置，求到达末尾的最大得分。

dp[i] = max(dp[j]) + nums[i]，j in [i-k, i-1]

用单调递减队列维护 dp[i-k..i-1] 的最大值：

public int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
 
    Deque<Integer> deque = new ArrayDeque<>();  // 单调递减队列，存下标
    deque.addLast(0);
 
    for (int i = 1; i < n; i++) {
        // 队首是 dp[i-k..i-1] 中的最大值下标
        while (!deque.isEmpty() && deque.peekFirst() < i - k) {
            deque.pollFirst();  // 滑出窗口
        }
        dp[i] = dp[deque.peekFirst()] + nums[i];  // 使用窗口内最大值
 
        // 维护单调递减：弹出所有比 dp[i] 小的元素
        while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
            deque.pollLast();
        }
        deque.addLast(i);
    }
    return dp[n - 1];
}

4.3 前缀和加速 DP

DP 转移中如果出现 sum(dp[l..r]) 或 max(dp[l..r])，可以用前缀和 / 前缀最值来优化：

// 优化前：O(n^2) 的转移
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] += dp[j];  // 求前缀和
    }
}
 
// 优化后：O(n) 的转移（维护前缀和 prefixSum）
int prefixSum = 0;
for (int i = 0; i < n; i++) {
    dp[i] = prefixSum + someValue;
    prefixSum += dp[i];
}

第 5 章面试中的 DP 决策树

5.1 快速识别流程图

题目要求最优值/计数？
    ↓ 是
输入是什么结构？
    ├─ 一维序列 → 线性 DP（House Robber, Coin Change）
    │              + 子序列？→ LIS/LCS 类
    ├─ 二维矩阵 → 矩阵路径 DP
    ├─ 字符串×字符串 → 双序列 DP（Edit Distance, 正则）
    ├─ 区间/合并 → 区间 DP（Burst Balloons）
    ├─ 树结构 → 树形 DP（DFS 后序）
    └─ 集合（n≤20） → 状态压缩 DP

有额外约束（如交易次数限制，冷冻期）？
    └─ 增加状态维度 → 状态机 DP

5.2 写代码前的五步检查

Step 1：确认状态定义。dp[i] 或 dp[i][j] 的完整含义，包括”考虑哪些元素”和”约束是什么”。

Step 2：确认转移方程。能够手动推导出 2-3 个状态的值，验证转移方程的正确性。

Step 3：确认初始化。Base case 的值是否正确；对于最小值问题，未定义的状态是否初始化为 MAX_VALUE。

Step 4：确认遍历顺序。是否每次计算 dp[i][j] 时，所有依赖的子问题都已经计算完毕。

Step 5：确认答案。答案在 dp[n]、max(dp[i]) 还是 dp[0][n-1]？不要直接返回 dp[n-1] 或 dp[n] 而不思考。

5.3 调试 DP 的方法

手动追踪：用一个小例子（3-5 个元素），手动填写 dp 表，对照代码输出，找到第一个不一致的格子。

打印 dp 数组：在提交前，临时添加打印 dp 数组的语句，确认每个格子的值是否符合预期。

单独验证 base case：先不运行主循环，只验证初始化的值是否正确。

第 6 章全系列高频题汇总

6.1 必须掌握的 20 道 DP 题（按重要性排序）

优先级	题号	题目	类型	关键点
⭐⭐⭐	70	Climbing Stairs	线性DP	入门，递推建立直觉
⭐⭐⭐	198	House Robber	线性DP	选或不选经典
⭐⭐⭐	300	LIS	子序列DP	$O (n^{2})$ + $O (n lo g n)$
⭐⭐⭐	322	Coin Change	完全背包	最少硬币数
⭐⭐⭐	72	Edit Distance	双序列DP	三方向转移
⭐⭐⭐	121	Best Time to Buy Sell Stock	状态机DP	一次交易
⭐⭐⭐	416	Partition Equal Subset Sum	0-1背包	判断能否恰好装满
⭐⭐⭐	62	Unique Paths	矩阵路径DP	入门，计数
⭐⭐	1143	LCS	双序列DP	两个字符串对比
⭐⭐	312	Burst Balloons	区间DP	逆向：枚举最后一个
⭐⭐	309	Stock with Cooldown	状态机DP	三状态
⭐⭐	518	Coin Change 2	完全背包	组合数
⭐⭐	10	Regular Expression	字符串DP	`*` 的两种用法
⭐⭐	516	Longest Palindromic Subsequence	区间DP	区间dp+回文
⭐⭐	123	Stock III (最多2次)	状态机DP	四状态链
⭐⭐	64	Min Path Sum	矩阵路径DP	最小代价
⭐	354	Russian Doll Envelopes	子序列DP	二维LIS
⭐	188	Stock IV (最多k次)	状态机DP	k维DP
⭐	337	House Robber III	树形DP	DFS后序
⭐	44	Wildcard Matching	字符串DP	`*` 匹配任意

6.2 各 DP 类型的空间复杂度优化路径

DP 类型	朴素空间	优化后	优化技巧
线性DP	$O (n)$	$O (1)$	滚动变量
0-1背包	$O (n \times W)$	$O (W)$	逆序一维数组
完全背包	$O (n \times W)$	$O (W)$	正序一维数组
双序列DP	$O (mn)$	$O (min (m, n))$	滚动行 + prev 变量
矩阵路径DP	$O (mn)$	$O (n)$	滚动行
区间DP	$O (n^{2})$	通常不可优化	-
状态压缩DP	$O (2^{n} \times n)$	视情况	-

第 7 章从入门到进阶的学习路径回顾

7.1 专栏文章全览

篇号	标题	核心能力
00	专栏导览	全景了解 DP 专栏体系
01	DP 思想导论	建立”递归→记忆化→DP表”的思维框架
02	一维线性 DP	掌握”选或不选”核心模式
03	背包问题	深刻理解 0-1 与完全背包的本质区别
04	子序列 DP	理解 LIS 的 $O (n lo g n)$ 优化
05	LCS 与编辑距离	掌握双序列 DP 的通用框架
06	矩阵路径 DP	熟练处理网格边界与反向 DP
07	区间 DP	理解”从小到大”遍历的必要性
08	字符串 DP 进阶	区分正则/通配符 `*` 的语义
09	树形/状压 DP	掌握 DFS 后序 + bitmask 集合枚举
10	综合通关	模式识别 + 买卖股票状态机 DP

7.2 DP 能力成长路径

第一阶段（入门）：
  - 能看懂 DP 解法并理解每个状态的含义
  - 能套用模板解决经典问题（爬楼梯、最大子数组、路径计数）

第二阶段（熟练）：
  - 能独立推导出转移方程
  - 对线性 DP、背包 DP、双序列 DP 不需要看提示
  - 能进行空间压缩优化

第三阶段（精通）：
  - 能识别题目类型并快速选择合适的 DP 框架
  - 能处理区间 DP、树形 DP 等高级变体
  - 能在面试高压环境下正确初始化和验证 DP

第四阶段（专家）：
  - 能证明 DP 的正确性（最优子结构、无后效性）
  - 能对 DP 进行高级优化（单调队列、斜率优化）
  - 能设计新颖问题的 DP 建模方案

小结

本文作为全系列的收官篇，完成了三个任务：

模式识别：七大 DP 模式的快速识别表，从题目关键词到 DP 类型的映射
买卖股票状态机 DP：从一次交易（贪心）到 k 次交易（完整状态机），逐步展示状态维度扩展的设计思路
综合总结：常见陷阱、调试技巧、DP 决策树、20 道必掌握高频题清单

至此，本专栏的核心内容全部覆盖。动态规划的本质是用空间换时间——把重叠子问题的结果存下来，避免重复计算。建立正确的状态定义是 DP 的基础，推导无后效性的转移方程是 DP 的核心，而面试中的 DP 能力最终体现在能否在 20 分钟内从问题描述出发，正确完成状态定义→转移方程→初始化→遍历顺序→答案位置的完整推导。

附录：全系列 LeetCode 题目对照表

题号	题目	所在章节	难度
70	Climbing Stairs	01 DP 导论	Easy
509	Fibonacci Number	01 DP 导论	Easy
746	Min Cost Climbing Stairs	01 DP 导论	Easy
198	House Robber	01/02	Medium
213	House Robber II	02	Medium
337	House Robber III	02/09	Medium
740	Delete and Earn	02	Medium
416	Partition Equal Subset Sum	03	Medium
322	Coin Change	03	Medium
518	Coin Change 2	03	Medium
474	Ones and Zeroes	03	Medium
377	Combination Sum IV	03	Medium
279	Perfect Squares	03	Medium
300	LIS	04	Medium
354	Russian Doll Envelopes	04	Hard
673	Number of LIS	04	Medium
1143	LCS	05	Medium
72	Edit Distance	05	Hard
97	Interleaving String	05	Medium
583	Delete Operation for Two Strings	05	Medium
115	Distinct Subsequences	05	Hard
62	Unique Paths	06	Medium
63	Unique Paths II	06	Medium
64	Min Path Sum	06	Medium
120	Triangle	06	Medium
174	Dungeon Game	06	Hard
312	Burst Balloons	07	Hard
664	Strange Printer	07	Hard
132	Palindrome Partitioning II	07	Hard
647	Palindromic Substrings	08	Medium
5	Longest Palindromic Substring	08	Medium
516	Longest Palindromic Subsequence	08	Medium
10	Regular Expression Matching	08	Hard
44	Wildcard Matching	08	Hard
968	Binary Tree Cameras	09	Hard
847	Shortest Path Visiting All Nodes	09	Hard
1125	Smallest Sufficient Team	09	Hard
691	Stickers to Spell Word	09	Hard
121	Best Time to Buy and Sell Stock	10	Easy
122	Best Time to Buy and Sell Stock II	10	Medium
309	Stock with Cooldown	10	Medium
714	Stock with Transaction Fee	10	Medium
123	Best Time to Buy and Sell Stock III	10	Hard
188	Best Time to Buy and Sell Stock IV	10	Hard
1696	Jump Game VI	10	Medium

汀的知识碎片

文章导航

10 动态规划综合通关：高频模式识别与面试决策树

动态规划综合通关：高频模式识别与面试决策树

摘要

第 1 章 DP 模式的快速识别

1.1 面试中识别 DP 问题的四个信号

1.2 七大 DP 模式速查表

1.3 从题目关键词快速定位 DP 类型

第 2 章状态机 DP：买卖股票系列

2.1 什么是状态机 DP

2.2 LeetCode 121：只允许一次交易

2.3 LeetCode 122：允许无限次交易

2.4 LeetCode 309：含冷冻期

2.5 LeetCode 714：含手续费

2.6 LeetCode 123：最多两次交易

2.7 LeetCode 188：最多 k 次交易

2.8 买卖股票系列总结

第 3 章常见陷阱与调试技巧

3.1 初始化错误

3.2 遍历顺序错误

3.3 状态定义模糊

3.4 整数溢出

第 4 章 DP 优化专题

4.1 滚动数组优化

4.2 单调队列优化滑动窗口 DP

4.3 前缀和加速 DP

第 5 章面试中的 DP 决策树

5.1 快速识别流程图

5.2 写代码前的五步检查

5.3 调试 DP 的方法

第 6 章全系列高频题汇总

6.1 必须掌握的 20 道 DP 题（按重要性排序）

6.2 各 DP 类型的空间复杂度优化路径

第 7 章从入门到进阶的学习路径回顾

7.1 专栏文章全览

7.2 DP 能力成长路径

小结

附录：全系列 LeetCode 题目对照表

On this page

汀的知识碎片

文章导航

10 动态规划综合通关：高频模式识别与面试决策树

动态规划综合通关：高频模式识别与面试决策树

摘要

第 1 章 DP 模式的快速识别

1.1 面试中识别 DP 问题的四个信号

1.2 七大 DP 模式速查表

1.3 从题目关键词快速定位 DP 类型

第 2 章 状态机 DP：买卖股票系列

2.1 什么是状态机 DP

2.2 LeetCode 121：只允许一次交易

2.3 LeetCode 122：允许无限次交易

2.4 LeetCode 309：含冷冻期

2.5 LeetCode 714：含手续费

2.6 LeetCode 123：最多两次交易

2.7 LeetCode 188：最多 k 次交易

2.8 买卖股票系列总结

第 3 章 常见陷阱与调试技巧

3.1 初始化错误

3.2 遍历顺序错误

3.3 状态定义模糊

3.4 整数溢出

第 4 章 DP 优化专题

4.1 滚动数组优化

4.2 单调队列优化滑动窗口 DP

4.3 前缀和加速 DP

第 5 章 面试中的 DP 决策树

5.1 快速识别流程图

5.2 写代码前的五步检查

5.3 调试 DP 的方法

第 6 章 全系列高频题汇总

6.1 必须掌握的 20 道 DP 题（按重要性排序）

6.2 各 DP 类型的空间复杂度优化路径

第 7 章 从入门到进阶的学习路径回顾

7.1 专栏文章全览

7.2 DP 能力成长路径

小结

附录：全系列 LeetCode 题目对照表

On this page

第 2 章状态机 DP：买卖股票系列

第 3 章常见陷阱与调试技巧

第 5 章面试中的 DP 决策树

第 6 章全系列高频题汇总

第 7 章从入门到进阶的学习路径回顾