线性 DP 复习笔记 - luohao 2026-05-31

---

1. 今日做题地图

题目	类型	今日情况	核心方法
统计回文子串数量	区间/线性 DP	4 次提交，最终 AC	f[l][r] 判断子串是否回文
摘花生	网格 DP	2 次提交，最终 AC	从上/左转移
数塔问题	路径 DP	6 次提交，最终 AC	从上一层相邻位置转移
最大子段和	最大子段 DP	3 次提交，最终 AC	Kadane：以 i 结尾的最大和
德育分-T2	最大子段变形	6 次提交，最终 AC	总和 + 最优连续段贡献
最大子阵和	二维压缩 + 最大子段	2 次提交，最终 AC	枚举上下边界，压成一维
双段最大子段和	前后缀 DP	4 次提交，最终 AC	左最大 + 右最大，枚举分界点
长度至少为 k 的最大子段和	前缀和/线性 DP	35 次提交，最终 AC	固定长度起步，再向后延长
判正负	计数 DP	8 次提交，最终 AC	以 i 结尾的正/负乘积区间数
大盗阿福	选择型 DP	6 次提交，最终 AC	选/不选当前店铺
环线	环形最大子段和	6 次提交，已做出核心思路	普通最大子段 / 总和 - 最小子段

---

2. 线性 DP 的通用思考框架

做线性 DP 时，先问自己 4 个问题：

1. 状态表示什么？

   • f[i] 通常表示「处理到第 i 个位置」或「必须以第 i 个位置结尾」。
   • 最大子段和里，f[i] 不是前 i 个数的最大答案，而是必须选到 a[i] 的最大连续段和。

2. 最后一步从哪里来？

   • 路径类：从上一个可到达位置来。
   • 连续段类：要么从前一段接上，要么从当前重新开始。
   • 选择类：选当前，则不能选相邻；不选当前，则继承上一位。

3. 答案是否等于 f[n]？

   • 不一定。
   • 最大子段和答案是 max(f[i])。
   • 双段最大子段和要枚举分界点。
   • 数塔答案是最后一层 max(f[n][j])。

4. 边界如何初始化？

   • 有负数时，ans 不能初始化为 0，要用很小的数，如 -1e18。
   • 多组数据时，数组和临时最大值要清空或重置。

---

3. 今日核心模型一：最大子段和

状态

f[i]：所有以第 i 个数结尾的连续子段中，最大和是多少。

转移

f[i] = max(a[i], f[i - 1] + a[i]);
ans = max(ans, f[i]);

含义：

• 如果前面的连续段拖后腿，就从 a[i] 重新开始。
• 如果前面的连续段有帮助，就接上 a[i]。

luohao 今日涉及题目

• 5357 最大子段和
• 5355 德育分-T2
• 5349 最大子阵和
• 5353 双段最大子段和
• 5664 长度至少为 k 的最大子段和
• 4386 环线

易错点

• 最大子段和的 ans 要边算边更新，或者最后扫一遍。
• 如果序列可能全是负数，不能让空子段参与答案。
• f[i] 的含义必须是「以 i 结尾」，否则很多变形题会写乱。

---

4. 今日核心模型二：长度至少为 k 的最大子段和

这题 luohao 今天提交了 35 次，说明它是今天最值得复盘的一题。

正确状态

f[i]：所有以 i 结尾，且长度至少为 k的连续子段最大和。

转移

sum[i] = sum[i - 1] + a[i];

if (i == k) {
    f[i] = sum[i];
}
if (i > k) {
    f[i] = max(sum[i] - sum[i - k], f[i - 1] + a[i]);
}
ans = max(ans, f[i]);

为什么这样转移？

以 i 结尾、长度至少为 k 的段只有两种来源：

1. 刚好长度为 k：

   • 区间 [i-k+1, i]
   • 和为 sum[i] - sum[i-k]

2. 超过长度 k：

   • 在一个已经合法的段后面接上 a[i]
   • 即 f[i-1] + a[i]

所以：

f[i] = max(刚好 k 个, 前一个合法段继续延长)

复习提醒

• 这题不是普通最大子段和，不能随便从 a[i] 重新开始，因为长度必须至少为 k。
• i < k 时没有合法答案。
• ans 初始值建议用 -1e18。

---

5. 今日核心模型三：双段最大子段和

题意关键词

选两个不重合的连续子段，使它们的和最大。

拆分思想

枚举分界点 i：

• 第一段完全在 [1, i]
• 第二段完全在 [i+1, n]

状态设计

f1[i] = 以 i 结尾的最大子段和
bestL[i] = [1, i] 内的最大子段和

f2[i] = 以 i 开始的最大子段和
bestR[i] = [i, n] 内的最大子段和

转移

f1[i] = max(a[i], f1[i - 1] + a[i]);
bestL[i] = max(bestL[i - 1], f1[i]);

f2[i] = max(a[i], f2[i + 1] + a[i]);
bestR[i] = max(bestR[i + 1], f2[i]);

ans = max(ans, bestL[i] + bestR[i + 1]);

易错点

• 枚举分界点时必须是 i < n。
• 两段不能重合，所以右段从 i+1 开始。
• 多组数据时，ans、bestL、bestR、f1、f2 都要重置。

---

6. 今日核心模型四：二维最大子阵和

降维思想

二维问题转成多次一维最大子段和。

固定上下边界 top, bottom，把每一列在这两行之间的和压成一维数组 b[col]：

b[col] = a[top][col] + a[top+1][col] + ... + a[bottom][col]

然后对 b 做一次最大子段和。

复杂度

• 枚举上下边界：O(n^2)
• 每次 Kadane：O(n)
• 总复杂度：O(n^3)

易错点

• 先想清楚压缩的是「行」还是「列」。
• ans 要能处理全负矩阵。
• b 每次换边界时都要重新计算或清空。

---

7. 今日核心模型五：路径 DP

摘花生

f[i][j]：走到格子 (i, j) 时最多能拿多少花生。

f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];

只允许从上面或左边来。

数塔问题

f[i][j]：走到第 i 层第 j 个点时的最大和。

f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

答案是最后一层最大值：

ans = max(f[n][1], f[n][2], ..., f[n][n]);

易错点

• 边界位置只有一个来源。
• 使用 1 下标时，数组默认 0 可能刚好能过正数题，但不是所有题都安全。
• 如果有负数，边界不能偷懒用 0。

---

8. 今日核心模型六：选择型 DP - 大盗阿福

状态

f[i]：前 i 家店铺中，在不偷相邻店铺的情况下，最多偷多少钱。

转移

f[i] = max(f[i - 1], f[i - 2] + a[i]);

含义：

• 不偷第 i 家：答案是 f[i-1]
• 偷第 i 家：第 i-1 家不能偷，答案是 f[i-2] + a[i]

边界

f[0] = 0;
f[1] = a[1];

复习提醒

这类题和最大子段和不同：

• 最大子段和要求选的是连续一段。
• 大盗阿福要求选的是若干不相邻位置，不要求连续。

---

9. 今日核心模型七：正负乘积区间计数

题目：统计乘积为负数、正数的连续子区间数量。

状态

neg[i]：以 i 结尾，乘积为负数的连续子区间个数。

pos[i]：以 i 结尾，乘积为正数的连续子区间个数。

转移

如果 a[i] > 0：

pos[i] = pos[i - 1] + 1;
neg[i] = neg[i - 1];

如果 a[i] < 0：

pos[i] = neg[i - 1];
neg[i] = pos[i - 1] + 1;

答案

ansPos += pos[i];
ansNeg += neg[i];

记忆方法

• 乘正数：正负性不变。
• 乘负数：正负性翻转。
• 单独的 a[i] 也要算一个区间。

---

10. 今日核心模型八：回文子串 DP

状态

f[l][r]：子串 s[l..r] 是否是回文串。

转移

f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];

边界

f[i][i] = true;
f[i][i + 1] = (s[i] == s[i + 1]);

枚举顺序

因为 f[l][r] 依赖 f[l+1][r-1]，所以要按长度从小到大枚举：

for (int len = 3; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];
    }
}

---

11. 今日核心模型九：环形最大子段和

环形最大子段和有两种情况：

1. 最大段不跨过首尾：普通最大子段和。
2. 最大段跨过首尾：等价于总和减去中间一段最小子段和。

ans1 = 最大子段和;
ans2 = sum - 最小子段和;
ans = max(ans1, ans2);

特别注意：全负数

如果所有数都是负数，sum - 最小子段和 可能变成空段，这是不允许的。

安全写法：

if (ans1 < 0) cout << ans1;
else cout << max(ans1, sum - minSubarray);

---

12. luohao 今天最需要巩固的 5 个点

1. 明确 f[i] 的含义

写 DP 前先在草稿上写一句话：

f[i] 表示 ________。

例如：

• f[i] 表示以 i 结尾的最大子段和。
• f[i] 表示前 i 家店铺的最大收益。
• f[i] 表示以 i 结尾、长度至少为 k 的最大子段和。

三句话长得像，但转移完全不同。

2. 有负数时，答案不能从 0 开始

如果题目允许负数，推荐：

long long ans = -4e18;

不要默认 ans = 0，否则全负数据会错。

3. 多组数据一定要重置

今天有多组数据的题：

• 双段最大子段和
• 大盗阿福

每组数据结束后要重置：

ans = -INF;
m1 = m2 = -INF;

数组如果下一组会被旧数据影响，也要清空关键范围。

4. 长度限制题不能随便重开

普通最大子段和可以：

f[i] = max(a[i], f[i - 1] + a[i]);

但长度至少为 k 时，不能从单个 a[i] 重开，因为长度不够。

5. 环形题要排除空段

sum - 最小子段和 的本质是选首尾两段，如果最小子段就是整个数组，会导致选空段。

全负数时直接输出普通最大子段和。

---

13. 考前速查模板

最大子段和

long long ans = -4e18;
for (int i = 1; i <= n; i++) {
    f[i] = max(a[i], f[i - 1] + a[i]);
    ans = max(ans, f[i]);
}

长度至少为 k 的最大子段和

long long ans = -4e18;
for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i];
    if (i == k) f[i] = sum[i];
    if (i > k) f[i] = max(sum[i] - sum[i - k], f[i - 1] + a[i]);
    if (i >= k) ans = max(ans, f[i]);
}

打家劫舍/大盗阿福

f[0] = 0;
f[1] = a[1];
for (int i = 2; i <= n; i++) {
    f[i] = max(f[i - 1], f[i - 2] + a[i]);
}
cout << f[n];

正负乘积区间

if (a[i] > 0) {
    pos[i] = pos[i - 1] + 1;
    neg[i] = neg[i - 1];
} else {
    pos[i] = neg[i - 1];
    neg[i] = pos[i - 1] + 1;
}
ansPos += pos[i];
ansNeg += neg[i];

环形最大子段和

maxEnd = minEnd = a[1];
maxAns = minAns = a[1];
sum = a[1];

for (int i = 2; i <= n; i++) {
    sum += a[i];
    maxEnd = max(a[i], maxEnd + a[i]);
    maxAns = max(maxAns, maxEnd);

    minEnd = min(a[i], minEnd + a[i]);
    minAns = min(minAns, minEnd);
}

if (maxAns < 0) cout << maxAns;
else cout << max(maxAns, sum - minAns);

---

14. 复习顺序建议

建议 luohao 按下面顺序复习，效率最高：

1. 先默写普通最大子段和。
2. 再默写长度至少为 k 的最大子段和，重点比较二者差异。
3. 复盘双段最大子段和，理解「左边最好 + 右边最好」。
4. 复盘最大子阵和，理解二维压缩成一维。
5. 最后复盘环形最大子段和，重点记住全负数特判。

---

15. 做题前 30 秒检查清单

• [ ] f[i] 的含义写清楚了吗？
• [ ] 答案是 f[n] 还是 max(f[i])？
• [ ] 是否有负数？ans 有没有初始化成极小值？
• [ ] 是否有多组数据？变量有没有重置？
• [ ] 是否有长度限制、不能随便从当前点重开？
• [ ] 是否有环形/不重合/相邻不能选等额外条件？

---

一句话总结：

线性 DP 的关键不是公式，而是先把 f[i] 的含义钉死。含义对了，转移就顺；含义模糊，提交次数就会变多。