02.7.1.4 线性 DP 进阶
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP
02.7.1.4-001 股票 I 一次交易(LC 121)怎么做?
一句话结论
遍历价格,维护历史最低价;当天卖出收益 price-min,全局取最大;等价一维 DP:dp[i] 前 i 天最大收益,转移 max(前一天收益, 当天价-历史最低);时间 O(n),空间 O(1)。
概念解释
- 一次交易:先买后卖。
- 状态:历史最低价与最大收益。
原理流程
- 定义前缀最大收益。
- 末步不卖取前一天,卖取当天价-最低价。
- 维护最低价与答案。
代码 / 示例
int min = Integer.MAX_VALUE, ans = 0;
for (int p : prices) {
min = Math.min(min, p);
ans = Math.max(ans, p - min);
}
常见误区
- 误区:先卖后买;正解:最低价必须在卖出日之前。
- 误区:空价格数组返回负收益;正解:不交易收益 0。
追问
- Q:复杂度? A:O(n) 时间 O(1) 空间。
- Q:能用 DP 状态机写吗? A:持有/未持有两状态,结果相同。
02.7.1.4-002 股票 II 多次交易(LC 122)怎么做?
一句话结论
不限制交易次数,只要后一天比前一天涨就累加差值;等价状态机:未持有可买入,持有可卖出,每日更新两状态;时间 O(n),空间 O(1)。
概念解释
- 多次买卖:同日可买卖衔接。
- 贪心差值:上涨段全部吃到。
原理流程
- 状态:持有/未持有最大收益。
- 每日更新转移。
- 末态未持有为答案。
代码 / 示例
int ans = 0;
for (int i = 1; i < prices.length; i++)
if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
常见误区
- 误区:一次高点全卖;正解:连续上涨可拆分累加,等价吃满波段。
- 误区:当天买卖同时计两次;正解:状态机内同日衔接合法。
追问
- Q:状态机怎么写? A:cash 未持有、hold 持有,每日互相转移。
- Q:复杂度? A:O(n)。
02.7.1.4-003 股票 III 最多两次交易(LC 123)怎么设计状态?
一句话结论
按交易次数与持股状态记状态:第 i 天完成 k 次交易的未持有、持有最大收益;枚举第 i 天买/卖;次数维度 0~2;时间 O(n·k),空间 O(k)。
概念解释
- 状态:天数 × 交易次数 × 持股。
- 买卖计入交易次数。
原理流程
- 定义各次交易下持有/未持有收益。
- 每日更新买入卖出转移。
- 末态未持有最大。
代码 / 示例
buy1/sell1/buy2/sell2 四个状态滚动更新
sell1 = max(sell1, buy1 + p);
buy2 = max(buy2, sell1 - p);
sell2 = max(sell2, buy2 + p);
常见误区
- 误区:两次交易可重叠;正解:先卖后买,交易不重叠。
- 误区:买入不计次数;正解:按卖出或买入约定计数并保持一致。
追问
- Q:复杂度? A:O(n·k),k=2 常数。
- Q:状态初始化? A:持有为 -INF,未持有 0。
02.7.1.4-004 股票 IV 最多 K 次(LC 188)怎么推广?
一句话结论
把 III 的次数维度推广到 k:dp[k][0/1] 完成 k 次交易未持有/持有;买入从 k-1 次未持有转持有,卖出从同次持有转未持有;k 超过 n/2 退化为 II 无限交易;时间 O(nk)。
概念解释
- 通用次数维。
- 退化:k 足够大即无限交易。
原理流程
- 建 k×2 状态表。
- 每日按次数更新买卖。
- 取 k 次内未持有最大。
代码 / 示例
// buy[t] 第 t 次持有;sell[t] 第 t 次未持有
for (int p : prices)
for (int t = 1; t <= k; t++) {
buy[t] = Math.max(buy[t], sell[t-1] - p);
sell[t] = Math.max(sell[t], buy[t] + p);
}
常见误区
- 误区:k 很大仍按 k 循环;正解:k≥n/2 退化为多次交易。
- 误区:买卖顺序同日覆盖;正解:用旧值更新或临时变量。
追问
- Q:复杂度? A:O(nk) 时间 O(k) 空间。
- Q:不可达状态怎么初始化? A:持有 -INF。
02.7.1.4-005 股票含冷冻期(LC 309)怎么加状态?
一句话结论
卖出后一天不能买入,需增加“冷冻”状态;三状态:未持有非冷冻、持有、冷冻(刚卖出);冷冻次日转未持有;买入只能来自非冷冻未持有;时间 O(n),空间 O(1)。
概念解释
- 冷冻期:卖出后隔一天。
- 状态扩展:第三类未持有。
原理流程
- 定义三状态收益。
- 卖出进入冷冻,冷冻转未持有。
- 买入来自非冷冻。
代码 / 示例
hold = max(hold, cash - p)
frozen = hold + p // 今日卖出
cash = max(cash, prevFrozen) // 冷冻结束转未持有
常见误区
- 误区:卖出次日即可买;正解:必须隔一天。
- 误区:冷冻状态与普通未持有混用;正解:分开记录来源。
追问
- Q:复杂度? A:O(n)。
- Q:冷冻期天数可推广吗? A:可扩展休息状态天数。
02.7.1.4-006 股票含手续费(LC 714)怎么扣减?
一句话结论
在卖出(或买入)时扣除手续费;状态机同 II,卖出收益 hold + p - fee;手续费只计一次交易;时间 O(n),空间 O(1)。
概念解释
- 成本:交易一次扣 fee。
- 转移:卖出时扣减。
原理流程
- 持有/未持有状态。
- 卖出扣手续费。
- 取末态未持有。
代码 / 示例
cash = Math.max(cash, hold + p - fee);
hold = Math.max(hold, cashPrev - p);
常见误区
- 误区:买卖各扣一次;正解:一笔交易只扣一次。
- 误区:用更新后的 cash 买当日;正解:保留前一日 cash。
追问
- Q:手续费在买入扣可以吗? A:可以,等价调整成本口径。
- Q:复杂度? A:O(n)。
02.7.1.4-007 股票状态机持有/未持有怎么设计?
一句话结论
每个交易日记两类状态:持有股票最大收益、未持有最大收益;买入从未持有转持有,卖出从持有转未持有;按题目限制(次数、冷冻期、手续费)扩展状态维度。
概念解释
- 持股状态:决策前提。
- 每日转移:买/卖/不动。
原理流程
- 定义持有、未持有收益。
- 每日枚举不动、买、卖。
- 末态未持有最优。
代码 / 示例
int hold = -prices[0], cash = 0;
for (int i = 1; i < n; i++) {
int newCash = Math.max(cash, hold + prices[i]);
int newHold = Math.max(hold, cash - prices[i]);
cash = newCash; hold = newHold;
}
常见误区
- 误区:更新时用当日新 cash 买入;正解:用前一日未持有值。
- 误区:末态取持有;正解:持有股票不如卖出变现。
追问
- Q:为什么持有初值 -INF? A:首日未买入不可持有。
- Q:状态机与贪心差值关系? A:II 状态机等价上涨累加。
02.7.1.4-008 打家劫舍 II 环形街区(LC 213)怎么拆?
一句话结论
首尾相邻不能同时偷,拆成两个线性问题:偷 0~n-2、偷 1~n-1,分别跑线性打家劫舍取最大;环形约束通过排除“首尾都选”覆盖。
概念解释
- 环形:首尾相邻。
- 拆分:两段线性区间。
原理流程
- 情况一不含尾。
- 情况二不含头。
- 两段结果取最大。
代码 / 示例
int robRange(int[] a, int l, int r) { /* 线性 DP */ }
return Math.max(robRange(a, 0, n-2), robRange(a, 1, n-1));
常见误区
- 误区:直接线性 DP 不管首尾;正解:首尾互斥必须拆分。
- 误区:两段区间边界写错;正解:一段去尾一段去头。
追问
- Q:n=1 怎么处理? A:直接返回该元素。
- Q:复杂度? A:O(n),两次线性 DP。
02.7.1.4-009 打家劫舍 III 树形(LC 337)为什么归树形 DP?
一句话结论
房子在二叉树上,父子不能同偷;后序递归每个节点返回“偷该节点”与“不偷该节点”两个值;偷则子节点不偷,不偷则子节点取各自最大;时间 O(n),详见 02.7.2.2。
概念解释
- 树形状态:节点选/不选。
- 后序合并子树。
原理流程
- 递归左右子树。
- 本层两状态合并。
- 返回两值给父层。
代码 / 示例
rob = left.notRob + right.notRob + val
notRob = max(left.rob,left.notRob) + max(right.rob,right.notRob)
常见误区
- 误区:按线性顺序偷;正解:父子约束在树上,需后序。
- 误区:只返回一个最大值;正解:需区分选/不选供父层用。
追问
- Q:复杂度? A:O(n) 时间 O(h) 栈。
- Q:与环形 II 区别? A:约束结构不同,树用树形 DP。
02.7.1.4-010 摆动序列(LC 376)怎么 DP?
一句话结论
两状态:以上升结尾、以下降结尾的最长摆动长度;当前价大于前价,上升状态来自前下降 +1;小于则下降来自前上升 +1;相等不变;时间 O(n),空间 O(1)。
概念解释
- 摆动:相邻涨跌交替。
- 结尾方向状态。
原理流程
- 记 up/down 长度。
- 按价差更新对应方向。
- 取两者最大。
代码 / 示例
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (p[i] > p[i-1]) up = down + 1;
else if (p[i] < p[i-1]) down = up + 1;
}
常见误区
- 误区:相等也更新长度;正解:持平不产生摆动。
- 误区:只记一个长度;正解:需区分结尾方向。
追问
- Q:复杂度? A:O(n)。
- Q:能贪心删平坡吗? A:等价,保留拐点即可。
02.7.1.4-011 最大子矩阵和怎么扩展一维?
一句话结论
枚举上下两行边界,把两行之间每列压缩成列和,问题转为一维最大子数组和;列和用前缀或逐行累加;时间 O(m²·n),空间 O(n)。
概念解释
- 压缩:多行压成列向量。
- 一维复用:最大子数组和。
原理流程
- 枚举上边界。
- 扩展下边界累加列和。
- 一维 DP 求最大。
代码 / 示例
for (int top = 0; top < m; top++) {
int[] colSum = new int[n];
for (int bottom = top; bottom < m; bottom++) {
// 累加第 bottom 行到 colSum,再 Kadane
}
}
常见误区
- 误区:直接二维枚举所有子矩阵;正解:压缩列和复用一维。
- 误区:列和未随上边界重置;正解:每个 top 重新累计。
追问
- Q:复杂度? A:O(m²n),行列可交换取较小平方。
- Q:全负矩阵答案? A:最大单元素。
02.7.1.4-012 三角形最小路径和(LC 120)怎么 DP?
一句话结论
dp[i][j] 到达三角第 i 行第 j 列最小路径和;来自上一行 j-1 或 j;可原地从底向上推;初始化末行即原值;时间 O(n²),空间 O(n)。
概念解释
- 路径:每行选一列,相邻列可达。
- 自底向上更省边界判断。
原理流程
- 从底向上累计。
- 每点取两前驱最小 + 当前值。
- 顶端即答案。
代码 / 示例
int[] dp = triangle.get(n-1).stream().mapToInt(x->x).toArray();
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
常见误区
- 误区:从上往下边界 j=0/j=i 漏处理;正解:自底向上更自然。
- 误区:前驱列越界;正解:边界只取合法一侧。
追问
- Q:复杂度? A:O(n²) 时间 O(n) 空间。
- Q:能原地改三角吗? A:可以,直接累加到原表。
02.7.1.4-013 解码方法(LC 91)怎么 DP?
一句话结论
dp[i] 前 i 个字符解码方法数;单字符合法则加 dp[i-1],两位数 10~26 则加 dp[i-2];初始化 dp[0]=1;正序;前导零单独判断。
概念解释
- 末步:解码一位或两位。
- 合法性:非零、范围 10~26。
原理流程
- 定义前缀方案数。
- 单字符与两位数分别转移。
- 非法前缀置 0。
代码 / 示例
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (s.charAt(i-1) != '0') dp[i] += dp[i-1];
if (i >= 2 && s.charAt(i-2) != '0' && Integer.parseInt(s.substring(i-2,i)) <= 26)
dp[i] += dp[i-2];
}
常见误区
- 误区:'0' 单独解码;正解:0 不能成码,只能并入两位。
- 误区:两位数前导零计入;正解:'0x' 非法。
追问
- Q:复杂度? A:O(n) 时间 O(1) 空间。
- Q:含 0 结尾怎么处理? A:必须与前位组成合法两位。
02.7.1.4-014 不同路径 I/II(LC 62/63)怎么做?
一句话结论
dp[i][j] 到达格子路径数;来自上方与左方;I 无障碍,II 障碍格置 0;初始化起点 1,第一行/列按可达性填;时间 O(mn),空间可滚 O(n)。
概念解释
- 移动:右、下。
- 障碍:不可达。
原理流程
- 定义格子路径数。
- 上左累加。
- 障碍格清零。
代码 / 示例
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (obstacle[i][j] == 1) { dp[i][j] = 0; continue; }
if (i > 0) dp[i][j] += dp[i-1][j];
if (j > 0) dp[i][j] += dp[i][j-1];
}
常见误区
- 误区:障碍格仍累加前驱;正解:直接置 0。
- 误区:起点是障碍未处理;正解:返回 0。
追问
- Q:复杂度? A:O(mn)。
- Q:组合数公式能解 I 吗? A:C(m+n-2, m-1),II 不行。
02.7.1.4-015 最小路径和(LC 64)怎么做?
一句话结论
dp[i][j] 到该格最小路径和;来自上/左最小加当前格;初始化起点为原值,第一行/列单向累加;时间 O(mn),空间可滚 O(n)。
概念解释
- 最值:路径和最小。
- 前驱:上、左。
原理流程
- 定义格子最小和。
- 前驱取最小加当前。
- 终点即答案。
代码 / 示例
dp[0][0] = grid[0][0];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i==0 && j==0) continue;
int up = i>0 ? dp[i-1][j] : INF;
int left = j>0 ? dp[i][j-1] : INF;
dp[i][j] = Math.min(up, left) + grid[i][j];
}
常见误区
- 误区:边界前驱越界取 0;正解:不可达用 INF。
- 误区:累加当前格两次;正解:当前格只加一次。
追问
- Q:复杂度? A:O(mn)。
- Q:能原地改 grid 吗? A:可以,省一维空间。
02.7.1.4-016 地牢游戏(LC 174)为什么反向 DP?
一句话结论
骑士到达终点时血量至少为 1,且途中不能降到 0 以下;从终点反向推:dp[i][j] 进入该格前所需最小血量,由后驱需求反推;正向 DP 无法同时保证全程血量,故反向。
概念解释
- 反向:从终点需求倒推起点。
- 血量约束:每步后 ≥1。
原理流程
- 终点需求血量 1。
- 每格由右/下需求反推。
- 起点所需即答案。
代码 / 示例
dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
常见误区
- 误区:正向求最大剩余血量;正解:正向无法保证中途不掉血,需反向需求。
- 误区:血量可低于 1;正解:每步至少 1。
追问
- Q:复杂度? A:O(mn)。
- Q:为什么取 min 后再 max(1)? A:选需求较小的后驱,且保底 1。
02.7.1.4-017 正则匹配(LC 10)状态怎么设计?
一句话结论
dp[i][j] 串前缀与模式前缀是否匹配;普通字符/. 对角匹配;* 可重复 0 次(跳模式两位)或多次(消耗串字符);初始化空串空模式为真;时间 O(mn)。
概念解释
- 模式:普通字符、
.、*。 - 星号:0 次或多次重复前字符。
原理流程
- 定义双前缀可行性。
- 按模式当前字符分类转移。
- 星号两种用法。
代码 / 示例
if (p[j-1] == '*') {
dp[i][j] = dp[i][j-2]; // 0 次
if (match(s[i-1], p[j-2])) dp[i][j] |= dp[i-1][j]; // 多次
} else if (match(...)) dp[i][j] = dp[i-1][j-1];
常见误区
- 误区:星号重复自身;正解:重复前一个模式字符。
- 误区:空串匹配边界漏填;正解:模式
a*可匹配空串。
追问
- Q:复杂度? A:O(mn) 空间可滚。
- Q:
.匹配什么? A:任意单字符。
02.7.1.4-018 通配符匹配(LC 44)与正则有何不同?
一句话结论
* 匹配任意长度任意串(不绑定前字符),? 匹配单字符;dp[i][j] 可行性;星号可用 0 次(跳模式)或多次(消耗串字符);转移比正则更直接。
概念解释
- 星号自由匹配。
- 问号单字符。
原理流程
- 双前缀可行性。
- 星号 0 次/多次转移。
- 问号/普通字符对角。
代码 / 示例
if (p[j-1] == '*') dp[i][j] = dp[i][j-1] || dp[i-1][j];
else if (s[i-1]==p[j-1] || p[j-1]=='?') dp[i][j] = dp[i-1][j-1];
常见误区
- 误区:把
*当正则绑定前字符;正解:通配符星号独立。 - 误区:多次转移用上一行未更新值;正解:按顺序核对。
追问
- Q:复杂度? A:O(mn)。
- Q:连续星号需要处理吗? A:等价一个星号,可预处理。
02.7.1.4-019 状态机 DP 怎么设计多状态?
一句话结论
把决策前提拆成互斥状态(持有/未持有、上升/下降、已选/未选),每个状态存当前最优值;每日/每步在状态间按合法转移更新;状态数由约束类别决定,转移枚举各合法动作。
概念解释
- 互斥状态:当前所处情形。
- 状态转移:动作触发状态切换。
原理流程
- 列出所有互斥情形。
- 每状态存最优值。
- 按动作更新转移。
代码 / 示例
状态:hold / cash;动作:买、卖、不动
常见误区
- 误区:多状态共用一个变量;正解:各状态分开记录。
- 误区:更新用当日新值导致同日多次交易;正解:保留旧值转移。
追问
- Q:状态太多怎么办? A:合并可推导状态或换题型。
- Q:状态初始化? A:不可达状态 -INF/false。
02.7.1.4-020 线性 DP 综合怎么选型?
一句话结论
先看问题是前缀、结尾还是容量视角,再列末步决策;单序列一维,双序列二维,状态带约束类别则加状态维;线性问题优先 DP,树形/区间/集合另归对应专题;报清状态数与转移代价。
概念解释
- 视角:前缀/结尾/容量。
- 维度:序列数与约束状态。
原理流程
- 判断题型归属。
- 选状态定义角度。
- 列转移、初始化、顺序与复杂度。
代码 / 图示
单序列一维;双序列二维;持股/方向加状态维
常见误区
- 误区:硬套股票模板到其他题;正解:状态按本题约束设计。
- 误区:忽略环形/树形结构;正解:结构特殊先归对应专题。
追问
- Q:线性 DP 状态数一般多少? A:O(n) 或 O(mn)。
- Q:什么时候考虑记忆化? A:状态稀疏或递归思路更自然时。