02.7.1.3 子序列问题
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP
02.7.1.3-001 子序列与子串有什么区别?
一句话结论
子序列不要求连续,保持相对顺序即可删除若干元素;子串/子数组必须连续;子序列 DP 常为二维状态 dp[i][j],子串问题多带结尾位置与连续性约束。
概念解释
- 子序列:顺序保留,可跳跃。
- 子串:连续区间。
原理流程
- 判断题目是否要求连续。
- 连续按区间/结尾处理。
- 不连续按子序列匹配转移。
代码 / 图示
"abcde" 子序列:"ace";子串:"bcd"
常见误区
- 误区:子序列必须相邻;正解:只需相对顺序。
- 误区:LCS 当连续匹配;正解:LCS 是子序列。
追问
- Q:最长重复子数组是哪种? A:连续,子数组。
- Q:子序列 DP 状态怎么设? A:两串前缀匹配状态。
02.7.1.3-002 最长递增子序列 LIS O(n²)(LC 300)怎么推?
一句话结论
dp[i] 以 i 结尾的 LIS 长度;枚举 j<i 且 a[j]<a[i],dp[i]=max(dp[j]+1, 1);初始化全 1;正序;全局取最大;时间 O(n²),空间 O(n)。
概念解释
- 结尾视角:必须含 a[i]。
- 前驱:更小值的结尾。
原理流程
- 定义结尾长度。
- 枚举前驱 j 转移。
- 全局取最大。
代码 / 示例
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
常见误区
- 误区:dp[i] 表示前 i 个最长;正解:结尾视角才好枚举前驱。
- 误区:相等元素也接上去;正解:严格递增用
<。
追问
- Q:返回哪个状态? A:遍历 dp 取最大。
- Q:复杂度? A:O(n²) 时间 O(n) 空间。
02.7.1.3-003 LIS O(n log n) tails 怎么维护?
一句话结论
tails[k] 表示长度 k+1 的递增子序列最小结尾;遍历 x,二分找第一个 ≥x 的位置替换,追加则长度 +1;tails 单调递增;时间 O(n log n),空间 O(n)。
概念解释
- 最小结尾:同长度留最小结尾更易扩展。
- 二分:找替换位置。
原理流程
- 维护 tails 数组。
- 每个 x 二分定位。
- 替换或追加。
代码 / 示例
int[] tails = new int[n];
int len = 0;
for (int x : a) {
int l = 0, r = len;
while (l < r) {
int m = (l + r) / 2;
if (tails[m] < x) l = m + 1; else r = m;
}
tails[l] = x;
if (l == len) len++;
}
常见误区
- 误区:tails 就是 LIS 本身;正解:只保结尾,序列需前驱还原。
- 误区:严格递增用 upper_bound;正解:严格递增找 ≥x(lower_bound)。
追问
- Q:最长不下降子序列怎么改? A:找 >x(upper_bound)。
- Q:tails 为什么单调? A:同长度结尾递增,长度越长结尾越大。
02.7.1.3-004 最长不下降子序列二分怎么改?
一句话结论
允许相等元素接续,二分找第一个 大于 x 的位置(upper_bound)替换;严格递增找 ≥x(lower_bound);比较符号变化决定相等是否可并入。
概念解释
- 不下降:相等可接续。
- upper_bound:首个大于 x。
原理流程
- 明确递增是否允许相等。
- 选 lower/upper 二分。
- 替换维护结尾。
代码 / 示例
// 不下降:tails[m] <= x 时右移,找 >x
if (tails[m] <= x) l = m + 1; else r = m;
常见误区
- 误区:两种序列用同一二分;正解:相等处理不同。
- 误区:替换位置越界;正解:追加时 len 增长。
追问
- Q:最长递减子序列? A:反转比较方向或取负数再 LIS。
- Q:长度怎么读? A:tails 有效长度 len。
02.7.1.3-005 最长公共子序列 LCS(LC 1143)怎么推?
一句话结论
dp[i][j] 前缀 a[0..i) 与 b[0..j) 的 LCS 长度;字符相等取 dp[i-1][j-1]+1,不等取 max(dp[i-1][j], dp[i][j-1]);初始化第 0 行/列为 0;正序填表;时间 O(mn),空间可滚 O(n)。
概念解释
- 双前缀状态。
- 末步:匹配/跳过某串字符。
原理流程
- 定义双前缀 LCS。
- 相等对角转移,不等上/左取大。
- 返回 dp[m][n]。
代码 / 示例
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
常见误区
- 误区:不等时也加对角;正解:不等只能跳过一侧。
- 误区:初始化漏掉空串边界;正解:第 0 行/列 0。
追问
- Q:空间能压到多少? A:一行数组滚动 O(n)。
- Q:怎么还原 LCS? A:二维表沿前驱回推。
02.7.1.3-006 最长重复子数组(LC 718)与 LCS 区别?
一句话结论
重复子数组要求连续,dp[i][j] 以两串末尾对齐的连续匹配长度;相等则 dp[i-1][j-1]+1,不等直接 0;全局取最大;LCS 不连续,不等仍保留上/左长度。
概念解释
- 连续:断了长度归零。
- 对齐结尾:必须两字符都在末尾。
原理流程
- 定义结尾对齐长度。
- 相等接续,不等归零。
- 全局最大。
代码 / 示例
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;
ans = Math.max(ans, dp[i][j]);
常见误区
- 误区:不等取上/左最大;正解:连续匹配断了要归零。
- 误区:返回 dp[m][n];正解:全局最大,结尾不一定在末尾。
追问
- Q:复杂度? A:O(mn),空间可滚 O(n)。
- Q:与 LCS 转移核心差异? A:不等分支处理不同。
02.7.1.3-007 编辑距离(LC 72)怎么推?
一句话结论
dp[i][j] a 前缀变 b 前缀最少操作数;相等取对角 dp[i-1][j-1],不等取替换/删除/插入三前驱最小 +1;初始化 dp[i][0]=i、dp[0][j]=j;正序;时间 O(mn),空间可滚 O(n)。
概念解释
- 三操作:替换、删 a、插 b。
- 双前缀状态。
原理流程
- 定义前缀编辑距离。
- 相等对角,不等三前驱取 min。
- 边界为空串操作数即长度。
代码 / 示例
if (a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
常见误区
- 误区:删除与插入前驱写反;正解:删 a 对应上一行,插 b 对应左一列。
- 误区:边界初始化成 0;正解:空串需逐字符增删。
追问
- Q:只允许插入删除对应什么? A:LCS 长度,m+n-2·LCS。
- Q:复杂度? A:O(mn)。
02.7.1.3-008 两串删除使相等(LC 583)怎么做?
一句话结论
删除后保留的公共部分即 LCS;最少删除数 = m + n - 2·LCS;先求 LCS 长度再换算;本质是 LCS 变体,不引入替换操作。
概念解释
- 保留公共子序列。
- 删除数 = 总长 - 2·保留长度。
原理流程
- 求 LCS。
- 两侧各删非公共部分。
- 换算删除总数。
代码 / 示例
int lcs = lcsLength(a, b);
return a.length() + b.length() - 2 * lcs;
常见误区
- 误区:直接编辑距离含替换;正解:本题只删不替。
- 误区:LCS 算成连续子串;正解:公共部分是子序列。
追问
- Q:与编辑距离关系? A:去掉替换操作的特例。
- Q:复杂度? A:O(mn)。
02.7.1.3-009 不相交线(LC 1035)为什么是 LCS 变体?
一句话结论
连线要求两数组下标递增且数值相等,连线不相交等价于求公共子序列;LCS 长度即最多不相交线数;转移与 LCS 完全一致。
概念解释
- 递增下标:子序列顺序。
- 不相交:对应 LCS 匹配。
原理流程
- 等价转 LCS。
- 双前缀 DP。
- 返回 LCS 长度。
代码 / 示例
相等:对角 +1;不等:上/左取大
常见误区
- 误区:连线可交叉重排;正解:下标顺序固定,即 LCS。
- 误区:相等就连线;正解:需按 LCS 最优选择。
追问
- Q:复杂度? A:O(mn)。
- Q:与 LCS 代码差别? A:无差别,题意不同。
02.7.1.3-010 最大上升子序列和怎么求?
一句话结论
dp[i] 以 i 结尾的最大上升子序列和;枚举 j<i 且 a[j]<a[i],dp[i]=max(a[i], dp[j]+a[i]);初始化 dp[i]=a[i];全局取最大;时间 O(n²)。
概念解释
- 目标:和而非长度。
- 结尾视角。
原理流程
- 定义结尾最大和。
- 合法前驱累加比较。
- 全局取最大。
代码 / 示例
dp[i] = a[i];
for (int j = 0; j < i; j++)
if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + a[i]);
常见误区
- 误区:初始化成 0;正解:单元素本身即一个子序列。
- 误区:相等元素接续;正解:上升严格
<。
追问
- Q:能用 tails 二分优化吗? A:求和目标不满足结尾单调性,一般 O(n²)。
- Q:复杂度? A:O(n²) 时间 O(n) 空间。
02.7.1.3-011 最长重复子串怎么求?
一句话结论
要求连续公共子串,可用 DP dp[i][j] 末尾对齐长度,相等 +1 不等归零,全局最大;也可用后缀数组/二分 + 哈希;DP 时间 O(mn)。
概念解释
- 连续子串。
- 末尾对齐状态。
原理流程
- 定义结尾对齐长度。
- 相等接续不等归零。
- 全局最大。
代码 / 示例
if (a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=0;
常见误区
- 误区:与 LCS 混淆取上/左;正解:连续归零。
- 误区:返回末态;正解:全局最大。
追问
- Q:单串最长重复子串? A:后缀排序或二分哈希。
- Q:DP 空间? A:可滚 O(n)。
02.7.1.3-012 子序列二维状态 dp[i][j] 怎么理解?
一句话结论
dp[i][j] 表示两个前缀(各前 i、j 个)下的目标值;i、j 分别对应两串位置,转移来自上一行、左一列、对角;填表按行优先,前驱均已就绪。
概念解释
- 双前缀:两个独立序列。
- 前驱:上/左/对角。
原理流程
- 定义双前缀含义。
- 列三类前驱转移。
- 行优先填表。
代码 / 图示
dp[i-1][j-1] 对角;dp[i-1][j] 上;dp[i][j-1] 左
常见误区
- 误区:行列对应同一串;正解:两串各一维。
- 误区:填表顺序反向;正解:i、j 均从小到大。
追问
- Q:能压成一维吗? A:保留上一行与对角值即可 O(n)。
- Q:状态数多少? A:O(mn)。
02.7.1.3-013 匹配相等与不等分别怎么转移?
一句话结论
两字符相等时通常走对角(同时消费两字符);不等时按题型跳过一侧(LCS 取上/左大)、归零(连续匹配)或三前驱取最小(编辑距离);先明确目标再选不等分支。
概念解释
- 相等:对角匹配。
- 不等:跳过/归零/多操作。
原理流程
- 判断当前字符是否匹配。
- 相等对角转移。
- 不等按题型选前驱。
代码 / 示例
LCS 不等:max(上,左);连续:0;编辑:三前驱 min+1
常见误区
- 误区:所有题不等都取上/左;正解:连续类归零。
- 误区:相等也比较上/左;正解:相等优先对角接续。
追问
- Q:相等为什么走对角? A:两字符都被消费并匹配。
- Q:转移遗漏前驱怎么办? A:对照小规模例子补齐。
02.7.1.3-014 LCS 路径怎么还原?
一句话结论
保留二维表,从 dp[m][n] 回推:相等则该字符属 LCS 且走向对角;不等则走向值较大的上或左;收集字符后反转即 LCS。
概念解释
- 前驱回推。
- 等值方向任选。
原理流程
- 从终态出发。
- 相等记录字符走对角。
- 不等走向大值前驱。
代码 / 示例
相等 → 收字符,i--,j--;不等 → 上/左取大者
常见误区
- 误区:压缩一维后还原;正解:需二维全表。
- 误区:等值方向处理不一致;正解:任选其一即可得到一条 LCS。
追问
- Q:多条 LCS 怎么全部输出? A:回溯枚举等值分支。
- Q:还原复杂度? A:O(m+n)。
02.7.1.3-015 不同子序列计数(LC 115)怎么推?
一句话结论
dp[i][j] 前 i 个源字符中出现子序列前 j 个的方案数;源字符相等时 dp[i-1][j-1]+dp[i-1][j](用/不用当前字符),不等只取 dp[i-1][j];初始化 dp[i][0]=1。
概念解释
- 计数:匹配方案数。
- 末步:用当前字符匹配或不用。
原理流程
- 定义双前缀计数。
- 相等两种选择累加。
- 不等仅不用当前。
代码 / 示例
if (s.charAt(i-1) == t.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
常见误区
- 误区:相等只算匹配;正解:不用当前字符的方案也要保留。
- 误区:dp[0][j] 初始 1;正解:空源串匹配非空子序列为 0。
追问
- Q:复杂度? A:O(mn),空间可滚 O(n)。
- Q:计数溢出? A:按题意取模。
02.7.1.3-016 单词拆分(LC 139)DP 怎么推?
一句话结论
dp[i] 前 i 个字符能否被词典拆分;枚举断点 j,若 dp[j] 为真且子串 [j,i) 在词典中则 dp[i]=true;初始化 dp[0]=true;正序;时间 O(n²) 加词典查询。
概念解释
- 前缀可行性。
- 断点枚举。
原理流程
- 定义前缀可拆分。
- 枚举最后一段起点 j。
- 词典命中且前缀可行则置真。
代码 / 示例
dp[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
常见误区
- 误区:dp[0] 初始 false;正解:空前缀可拆分。
- 误区:子串区间写错;正解:[j,i)。
追问
- Q:复杂度? A:O(n²),子串哈希/词典 O(1) 平均。
- Q:记忆化回溯等价吗? A:等价,状态为起点 i。
02.7.1.3-017 最长回文子序列(LC 516)怎么推?
一句话结论
dp[i][j] 区间 [i,j] 最长回文子序列;两端相等取 dp[i+1][j-1]+2,不等取 max(dp[i+1][j], dp[i][j-1]);初始化 len=1 为 1;按区间长度外层;时间 O(n²)。
概念解释
- 区间状态。
- 两端匹配/省略。
原理流程
- 定义区间回文长度。
- 相等两端纳入,不等舍一端。
- 长度递增填表。
代码 / 示例
for (int len = 2; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
常见误区
- 误区:按 i 正序填;正解:区间长度外层,依赖更短区间。
- 误区:相等时漏 +2;正解:两端各计一个字符。
追问
- Q:复杂度? A:O(n²) 时间空间。
- Q:与最长回文子串区别? A:子序列不连续,子串连续。
02.7.1.3-018 最长回文子串与子序列 DP 怎么区分?
一句话结论
回文子串连续,中心扩展或区间 DP 判连续性;回文子序列不连续,区间 DP 可舍端点;前者断了不接续,后者两端不等可保留内部;按是否连续选方法。
概念解释
- 连续:子串。
- 不连续:子序列。
原理流程
- 判断题面是否连续。
- 连续用中心扩展/连续区间。
- 不连续用子序列 DP。
代码 / 图示
子串:dp[i][j] 两端相等且内部为回文;子序列:不等可舍端
常见误区
- 误区:子串问题用子序列转移;正解:连续性要求内部连续回文。
- 误区:中心扩展报 DP 复杂度;正解:中心扩展 O(n²) 时间 O(1) 空间。
追问
- Q:回文子串区间 DP 怎么判? A:两端相等且内部区间为回文。
- Q:两者状态都区间吗? A:是,依赖顺序不同。
02.7.1.3-019 子序列问题复杂度 m×n 怎么报?
一句话结论
双串子序列状态 O(mn),单状态 O(1) 转移,时间 O(mn);一维滚动空间 O(n);单串 LIS O(n²) 或 tails O(n log n);先数两串长度再乘转移代价。
概念解释
- 双串状态:m×n。
- 单串状态:n。
原理流程
- 判断单串/双串。
- 数状态维度。
- 乘单状态转移。
代码 / 示例
LCS/编辑:O(mn);LIS:O(n²) 或 O(n log n)
常见误区
- 误区:双串 DP 报 O(n);正解:两长度都在状态里。
- 误区:忽略子串生成代价;正解:计数/还原另计。
追问
- Q:空间滚动怎么做? A:只留上一行。
- Q:状态稀疏用记忆化? A:可,按可达状态估。
02.7.1.3-020 子序列问题常见误区有哪些?
一句话结论
高频误区:子串与子序列混淆、连续断了不归零、初始化边界漏空串、结尾视角未全局取最大、LCS 不等分支写错、还原方案未留二维表;按连续性与状态定义逐项核对。
概念解释
- 连续性:是否归零。
- 边界:空串/单字符。
原理流程
- 先确认连续与否。
- 核对边界初始化。
- 检查不等分支与返回状态。
代码 / 示例
排查:连续/子序列 / 边界 / 不等分支 / 返回取值 / 二维留表
常见误区
- 误区:相等一律对角 +1;正解:按题型决定不等分支。
- 误区:dp[m][n] 当所有题答案;正解:结尾/连续类要全局最大。
追问
- Q:结果偏小先查什么? A:不等分支是否漏前驱。
- Q:结果偏大先查什么? A:连续问题是否错误保留上/左。