第 25 站 · 动态规划
子序列与偏序关系
LIS：tails 数组 + 二分 O(n log n)
- 先学
- 学完去
- 面试频次
- 2 家公司考过 · 面经出现 2 次Experian 1、TikTok / ByteDance 1
先做这道
LC 300最长递增子序列卡住再看
先建立二次DP，再解释最小末尾数组加二分为何能求长度。
要点
- tails[k] 是长度为 k+1 的递增子序列可能的最小结尾；它本身是递增的，所以可以二分。
- 严格递增用 lower_bound（第一个 ≥ x），非递减用 upper_bound（第一个 > x）。
- 二维的「信封嵌套」先按宽升序、宽相同时按高降序排序，再对高做 LIS。
易错点
- tails 数组不是真实存在的最长子序列，只有长度是对的；要输出方案得另外记录前驱。
- 严格和非严格用错了二分函数，重复元素多的用例会差 1 甚至更多。
- 要求「最长子序列有几个」时，O(n log n) 写法不够，要回到 O(n²) 的 dp 加计数数组。
看动画
一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。
二维 DP · 填表求最长公共子序列
「ACBD」和「ABCD」的最长公共子序列
换个输入
∅
A
B
C
D
∅
00,0
00,1
00,2
00,3
00,4
A
01,0
·1,1
·1,2
·1,3
·1,4
C
02,0
·2,1
·2,2
·2,3
·2,4
B
03,0
·3,1
·3,2
·3,3
·3,4
D
04,0
·4,1
·4,2
·4,3
·4,4
当前处理已发现 / 已计算答案
- LCS 长度
- —
dp[i][j] 是「ACBD」前 i 个字符与「ABCD」前 j 个字符的最长公共子序列长度。第 0 行和第 0 列是空串，都为 0。
始终成立按行从左到右填：算 dp[i][j] 时，它依赖的上方、左方、左上方都已算好。
模板
选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 300。
Python
from bisect import bisect_left
def lis_length(nums: list[int]) -> int:
"""Length of the longest strictly increasing subsequence."""
tails = [] # tails[k]: smallest tail of an increasing subsequence of length k+1
for x in nums:
i = bisect_left(tails, x) # bisect_right for non-decreasing
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)C++
// Length of the longest strictly increasing subsequence.
int lisLength(const vector<int>& nums) {
vector<int> tails; // tails[k]: smallest tail of an increasing subsequence of length k+1
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x); // upper_bound for non-decreasing
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}Java
class Solution {
// Length of the longest strictly increasing subsequence.
int lisLength(int[] nums) {
int[] tails = new int[nums.length]; // tails[k]: smallest tail of length k+1
int len = 0;
for (int x : nums) {
int lo = 0, hi = len; // first index with tails[i] >= x (use > for non-decreasing)
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] >= x) hi = mid;
else lo = mid + 1;
}
tails[lo] = x;
if (lo == len) len++;
}
return len;
}
}Go
import "sort"
// lisLength returns the length of the longest strictly increasing subsequence.
func lisLength(nums []int) int {
var tails []int // tails[k]: smallest tail of an increasing subsequence of length k+1
for _, x := range nums {
i := sort.SearchInts(tails, x) // first index with tails[i] >= x
if i == len(tails) {
tails = append(tails, x)
} else {
tails[i] = x
}
}
return len(tails)
}常见变体
这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。
O(n²) LIS：同时记长度和条数时间 O(n²) · 空间 O(n)
不只要 LIS 的长度，还要条数、或者要还原出一条具体的序列时，tails 数组不够用，退回 O(n²)：length[i] 是以 i 结尾的最长长度，count[i] 是这样的条数，遇到更长的就接管计数，一样长就累加。LC 673 最长递增子序列的个数；LC 368、LC 1048、LC 646 是同一个双重循环。
Python
def count_lis(nums: list[int]) -> int:
"""Number of longest strictly increasing subsequences (LC 673)."""
n = len(nums)
length = [1] * n # length[i]: longest increasing subsequence ending at i
count = [1] * n # count[i]: how many of that length end at i
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if length[j] + 1 > length[i]: # longer: take over j's count
length[i], count[i] = length[j] + 1, count[j]
elif length[j] + 1 == length[i]: # as long: add j's count
count[i] += count[j]
best = max(length)
return sum(c for l, c in zip(length, count) if l == best)C++
// Number of longest strictly increasing subsequences (LC 673).
long long countLis(const vector<int>& nums) {
int n = nums.size();
vector<int> length(n, 1); // length[i]: longest increasing subsequence ending at i
vector<long long> count(n, 1); // count[i]: how many of that length end at i
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) {
if (nums[j] >= nums[i]) continue;
if (length[j] + 1 > length[i]) { // longer: take over j's count
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[j] + 1 == length[i]) { // as long: add j's count
count[i] += count[j];
}
}
int best = *max_element(length.begin(), length.end());
long long total = 0;
for (int i = 0; i < n; i++)
if (length[i] == best) total += count[i];
return total;
}Java
class Solution {
// Number of longest strictly increasing subsequences (LC 673).
long countLis(int[] nums) {
int n = nums.length, best = 0;
int[] length = new int[n]; // length[i]: longest increasing subsequence ending at i
long[] count = new long[n]; // count[i]: how many of that length end at i
for (int i = 0; i < n; i++) {
length[i] = 1;
count[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] >= nums[i]) continue;
if (length[j] + 1 > length[i]) { // longer: take over j's count
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[j] + 1 == length[i]) { // as long: add j's count
count[i] += count[j];
}
}
best = Math.max(best, length[i]);
}
long total = 0;
for (int i = 0; i < n; i++)
if (length[i] == best) total += count[i];
return total;
}
}Go
// countLis returns the number of longest strictly increasing subsequences (LC 673).
func countLis(nums []int) int {
n := len(nums)
length, count := make([]int, n), make([]int, n) // longest ending at i, and how many of that length
best := 0
for i := range nums {
length[i], count[i] = 1, 1
for j := 0; j < i; j++ {
if nums[j] >= nums[i] {
continue
}
if length[j]+1 > length[i] { // longer: take over j's count
length[i], count[i] = length[j]+1, count[j]
} else if length[j]+1 == length[i] { // as long: add j's count
count[i] += count[j]
}
}
best = max(best, length[i])
}
total := 0
for i := range nums {
if length[i] == best {
total += count[i]
}
}
return total
}按值索引的 DP：哈希表代替下标时间 O(n) · 空间 O(n)
子序列的相邻关系由「值」决定（公差固定的等差子序列、斐波那契式子序列）时，状态按值存进哈希表：以 x 结尾的最长长度等于以 x - d 结尾的加一，一遍 O(n)。LC 1218 最长定差子序列；LC 1027、LC 873 把公差或前两项也放进键里。
Python
def longest_arith_subseq(arr: list[int], difference: int) -> int:
"""Longest subsequence whose neighbours differ by exactly difference (LC 1218)."""
best_end: dict[int, int] = {} # value -> longest such subsequence ending with that value
best = 0
for x in arr:
best_end[x] = best_end.get(x - difference, 0) + 1 # extend the one ending at x - difference
best = max(best, best_end[x])
return bestC++
// Longest subsequence whose neighbours differ by exactly difference (LC 1218).
int longestArithSubseq(const vector<int>& arr, int difference) {
unordered_map<int, int> bestEnd; // value -> longest such subsequence ending with that value
int best = 0;
for (int x : arr) {
auto it = bestEnd.find(x - difference);
int len = (it == bestEnd.end() ? 0 : it->second) + 1; // extend the one ending at x - difference
bestEnd[x] = len;
best = max(best, len);
}
return best;
}Java
class Solution {
// Longest subsequence whose neighbours differ by exactly difference (LC 1218).
int longestArithSubseq(int[] arr, int difference) {
Map<Integer, Integer> bestEnd = new HashMap<>(); // value -> longest such subsequence ending with that value
int best = 0;
for (int x : arr) {
int len = bestEnd.getOrDefault(x - difference, 0) + 1; // extend the one ending at x - difference
bestEnd.put(x, len);
best = Math.max(best, len);
}
return best;
}
}Go
// longestArithSubseq returns the longest subsequence whose neighbours differ by exactly difference.
func longestArithSubseq(arr []int, difference int) int {
bestEnd := map[int]int{} // value -> longest such subsequence ending with that value
best := 0
for _, x := range arr {
bestEnd[x] = bestEnd[x-difference] + 1 // extend the one ending at x - difference
best = max(best, bestEnd[x])
}
return best
}为什么对
- tails 严格递增：长度为 k+1 的递增子序列去掉最后一个元素，得到一个结尾更小的长度为 k 的子序列，所以 tails[k] < tails[k+1]，可以二分。
- 用 x 替换第一个 ≥ x 的位置，只会让某个长度的最小结尾变小，不改变已达到的最大长度；结尾越小越容易被后面的数接上，所以这个贪心不会让答案变差。
- tails 本身通常不是一个真实的子序列，只有它的长度是答案；要输出序列，需要另外记录前驱。
30 秒口述稿
面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。
最长递增子序列我用 O(n log n) 的做法：维护 tails，tails[k] 是长度为 k+1 的递增子序列可能的最小结尾。它本身递增，所以每来一个数就二分找第一个大于等于它的位置替换，找不到就追加。结尾越小越容易被后面接上，所以替换不会让答案变差，最后 tails 的长度就是答案。要求非严格递增时把 lower_bound 换成 upper_bound。For the longest increasing subsequence I use the O(n log n) method with an array tails, where tails[k] is the smallest possible end of an increasing subsequence of length k + 1. tails is itself sorted, so for each number I binary search the first entry at least as large and replace it, or append when there is none. A smaller end is easier to extend, so replacing never hurts, and the final length of tails is the answer. For non-decreasing subsequences I use upper bound instead of lower bound.自评一下
对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。
小测
3 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习
作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。
模板练习
用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。
下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。
分档练习
本站在 500 路里的 11 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。
核心 5
进阶 6
| # | 题目 | 一句话思路 | 难度分 |
|---|---|---|---|
| 673 | 最长递增子序列的个数 | 同时维护最优长度与方案数，区分更优状态覆盖和等长状态累加。 | |
| 354 | 俄罗斯套娃信封问题 | 利用同宽逆序排序消除伪链，把二维严格偏序降为一维LIS。 | |
| 1027 | 最长等差数列 | 当差值未知时把公差加入状态，训练从一维状态扩展到二维映射。 | |
| 873 | 最长的斐波那契子序列的长度 | 以前两项确定下一项，理解为什么需要保存一对下标而非单一末尾值。 | |
| 1626 | 无矛盾的最佳球队 | 通过排序处理年龄与分数冲突，构造带权最长非降子序列。 | |
| 1671 | 得到山形数组的最少删除次数 | 合并左右两个方向的LIS，要求峰顶两侧都非空，避免接受单调序列。 |
本站 OA 真题 27
- Domino Removal ProblemAmazon
- Get Max Matching (Match the Column)Amazon
- countSecurePasswordVariationsAmazon
- Count Secured StringsAmazon
- Maximize Parentheses Efficiency ScoreAmazon
- Maximum Domino RemovalsAmazon
- Minimum Insertions to Make List a Subsequence (Amazon Germany :)Amazon
- Min Num LettersMicrosoft
- Minimum Domino RemovalsMicrosoft
- Minimum Cars to RemoveMicrosoft