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

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)。

概念解释

  • 一次交易:先买后卖。
  • 状态:历史最低价与最大收益。

原理流程

  1. 定义前缀最大收益。
  2. 末步不卖取前一天,卖取当天价-最低价。
  3. 维护最低价与答案。

代码 / 示例

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)。

概念解释

  • 多次买卖:同日可买卖衔接。
  • 贪心差值:上涨段全部吃到。

原理流程

  1. 状态:持有/未持有最大收益。
  2. 每日更新转移。
  3. 末态未持有为答案。

代码 / 示例

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)。

概念解释

  • 状态:天数 × 交易次数 × 持股。
  • 买卖计入交易次数。

原理流程

  1. 定义各次交易下持有/未持有收益。
  2. 每日更新买入卖出转移。
  3. 末态未持有最大。

代码 / 示例

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 足够大即无限交易。

原理流程

  1. 建 k×2 状态表。
  2. 每日按次数更新买卖。
  3. 取 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)。

概念解释

  • 冷冻期:卖出后隔一天。
  • 状态扩展:第三类未持有。

原理流程

  1. 定义三状态收益。
  2. 卖出进入冷冻,冷冻转未持有。
  3. 买入来自非冷冻。

代码 / 示例

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。
  • 转移:卖出时扣减。

原理流程

  1. 持有/未持有状态。
  2. 卖出扣手续费。
  3. 取末态未持有。

代码 / 示例

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 股票状态机持有/未持有怎么设计?

一句话结论

每个交易日记两类状态:持有股票最大收益、未持有最大收益;买入从未持有转持有,卖出从持有转未持有;按题目限制(次数、冷冻期、手续费)扩展状态维度。

概念解释

  • 持股状态:决策前提。
  • 每日转移:买/卖/不动。

原理流程

  1. 定义持有、未持有收益。
  2. 每日枚举不动、买、卖。
  3. 末态未持有最优。

代码 / 示例

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,分别跑线性打家劫舍取最大;环形约束通过排除“首尾都选”覆盖。

概念解释

  • 环形:首尾相邻。
  • 拆分:两段线性区间。

原理流程

  1. 情况一不含尾。
  2. 情况二不含头。
  3. 两段结果取最大。

代码 / 示例

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。

概念解释

  • 树形状态:节点选/不选。
  • 后序合并子树。

原理流程

  1. 递归左右子树。
  2. 本层两状态合并。
  3. 返回两值给父层。

代码 / 示例

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)。

概念解释

  • 摆动:相邻涨跌交替。
  • 结尾方向状态。

原理流程

  1. 记 up/down 长度。
  2. 按价差更新对应方向。
  3. 取两者最大。

代码 / 示例

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)。

概念解释

  • 压缩:多行压成列向量。
  • 一维复用:最大子数组和。

原理流程

  1. 枚举上边界。
  2. 扩展下边界累加列和。
  3. 一维 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)。

概念解释

  • 路径:每行选一列,相邻列可达。
  • 自底向上更省边界判断。

原理流程

  1. 从底向上累计。
  2. 每点取两前驱最小 + 当前值。
  3. 顶端即答案。

代码 / 示例

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。

原理流程

  1. 定义前缀方案数。
  2. 单字符与两位数分别转移。
  3. 非法前缀置 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)。

概念解释

  • 移动:右、下。
  • 障碍:不可达。

原理流程

  1. 定义格子路径数。
  2. 上左累加。
  3. 障碍格清零。

代码 / 示例

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)。

概念解释

  • 最值:路径和最小。
  • 前驱:上、左。

原理流程

  1. 定义格子最小和。
  2. 前驱取最小加当前。
  3. 终点即答案。

代码 / 示例

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. 终点需求血量 1。
  2. 每格由右/下需求反推。
  3. 起点所需即答案。

代码 / 示例

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 次或多次重复前字符。

原理流程

  1. 定义双前缀可行性。
  2. 按模式当前字符分类转移。
  3. 星号两种用法。

代码 / 示例

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 次(跳模式)或多次(消耗串字符);转移比正则更直接。

概念解释

  • 星号自由匹配。
  • 问号单字符。

原理流程

  1. 双前缀可行性。
  2. 星号 0 次/多次转移。
  3. 问号/普通字符对角。

代码 / 示例

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 怎么设计多状态?

一句话结论

把决策前提拆成互斥状态(持有/未持有、上升/下降、已选/未选),每个状态存当前最优值;每日/每步在状态间按合法转移更新;状态数由约束类别决定,转移枚举各合法动作。

概念解释

  • 互斥状态:当前所处情形。
  • 状态转移:动作触发状态切换。

原理流程

  1. 列出所有互斥情形。
  2. 每状态存最优值。
  3. 按动作更新转移。

代码 / 示例

状态:hold / cash;动作:买、卖、不动

常见误区

  • 误区:多状态共用一个变量;正解:各状态分开记录。
  • 误区:更新用当日新值导致同日多次交易;正解:保留旧值转移。

追问

  • Q:状态太多怎么办? A:合并可推导状态或换题型。
  • Q:状态初始化? A:不可达状态 -INF/false。

02.7.1.4-020 线性 DP 综合怎么选型?

一句话结论

先看问题是前缀、结尾还是容量视角,再列末步决策;单序列一维,双序列二维,状态带约束类别则加状态维;线性问题优先 DP,树形/区间/集合另归对应专题;报清状态数与转移代价。

概念解释

  • 视角:前缀/结尾/容量。
  • 维度:序列数与约束状态。

原理流程

  1. 判断题型归属。
  2. 选状态定义角度。
  3. 列转移、初始化、顺序与复杂度。

代码 / 图示

单序列一维;双序列二维;持股/方向加状态维

常见误区

  • 误区:硬套股票模板到其他题;正解:状态按本题约束设计。
  • 误区:忽略环形/树形结构;正解:结构特殊先归对应专题。

追问

  • Q:线性 DP 状态数一般多少? A:O(n) 或 O(mn)。
  • Q:什么时候考虑记忆化? A:状态稀疏或递归思路更自然时。