最长递增子序列
动态规划 · 一维 DP
最长的一段「越来越大」
给一串数 [1, 3, 2, 4, 3, 5]，找一个最长的子序列（按顺序挑，不要求连续），让它严格递增。这里的答案是 1 → 3 → 4 → 5（长度 4）。这仍是动态规划，但和前几页不同——它的 DP 表是一维的。
一维 DP：dp[i] 只回看前面
设 dp[i] 为以第 i 个数结尾的最长递增子序列长度。每个数单独成序列，所以 dp 全部从 1 起。填 dp[i] 时，回看前面每一个 j < i：只要 a[j] < a[i]（能接在 a[j] 后面继续变大），就用 dp[j] + 1 更新 dp[i]，取所有这样的 j 里最大的。前几页 DP 依赖「上/左/左上」的相邻格，这里 dp[i] 依赖前面所有 dp[j]——这就是一维 DP 的味道。
全部填完后，最大的 dp[i] 就是 LIS 的长度。想恢复出具体是哪几个数，和 LCS 一样从最大值处回溯：记住每个 dp[i] 是从哪个 j 接过来的（前驱），沿前驱倒着串起来即可。
下面是 [1, 3, 2, 4, 3, 5] 的 DP 两行表（上行是值、下行是 dp）。点「下一步」逐步看：当前 i（琥珀）逐个回看每个 j（黄色），能变长就把 dp[i] 增大（绿色）；填完后从最大 dp 回溯，构成 LIS 的元素绿环标出。右侧代码随每一步同步高亮。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 值 | 1 | 3 | 2 | 4 | 3 | 5 |
| dp | 1 | 1 | 1 | 1 | 1 | 1 |
每个元素自身是长度 1 的递增子序列：dp 全部初始化为 1
1function longestIncreasingSubseq(a: number[]): number[] {
2 const n = a.length;
3 const dp = new Array(n).fill(1); // 每个元素自身长度 1
4 const pred = new Array(n).fill(-1);
5 for (let i = 1; i < n; i++) {
6 for (let j = 0; j < i; j++) {
7 if (a[j] < a[i] && dp[j] + 1 > dp[i]) { // 能接得更长
8 dp[i] = dp[j] + 1;
9 pred[i] = j;
10 }
11 }
12 }
13 let best = 0;
14 for (let i = 1; i < n; i++) if (dp[i] > dp[best]) best = i; // 最长在哪结尾
15 const lis: number[] = [];
16 for (let k = best; k !== -1; k = pred[k]) lis.unshift(a[k]); // 回溯恢复
17 return lis;
18}
输入1 3 2 4 3 5
dp1 1 1 1 1 1
1 / 18
一维 vs 二维
本页的 O(n²) 解法最直观（每个 i 回看所有 j）；LIS 还有更快的 O(n log n) 解法（维护一个「各长度下最小结尾」的数组 + 二分），但一维 DP 已足够把「回看前面、取最优、再回溯恢复」讲清楚。它与LCS同属「子序列」家族，一个在两串间、一个在一串内。