动态规划
最近面试复习，发现已经完全失去了写 DP 迭代的能力，无奈只能从零学起。
最长递增子序列
求一个数列的最长递增子序列（的长度），我第一时间想到的解法是：
const solveAsc = (i: number, queue: number[]): number => {
// 1. 越界检查
if (i === students.length) return queue.length;
// 2. 选择 A：跳过 students[i]
let max = solveAsc(i + 1, [...queue]);
// 3. 选择 B：包含 students[i]（如果合法）
const last = queue[queue.length - 1];
if (queue.length === 0 || students[i] > last) {
const m = solveAsc(i + 1, [...queue, students[i]]);
max = Math.max(max, m);
}
return max;
};相当于先展开到各分支的叶子节点，返回该分支的最终序列长度，然后层层上浮，每一层和兄弟节点的长度PK。
显然这里参数和返回值有重合之处，queue本身也携带了长度信息。一般而言，递归版本和DP版本存在如下的对应关系：
| 递归 | DP |
|---|---|
| 参数 | 表的索引（迭代状态） |
| 返回值 | 表里存的值（结果） |
| 函数体逻辑 | 状态转移方程 |
我们已经能够用返回值表达序列长度，就不需要在参数里维护完整的queue（参数queue其实是两个维度，长度和最值），只需要维护其中的最大值last即可。然而尝试优化的时候我们会遇到困难，如果参数里只携带last，递归到边界情况时，没有完整的该分支queue，原本if (i === students.length) return queue.length;，那现在该返回什么呢？
这里的问题在于遍历顺序，solveAsc(i + 1, [...queue, students[i]])，在下钻之前先push自己到序列中，这是典型的先序遍历特征，到叶子时可以拿到完整序列。要想实现不携带完整序列也能统计，需要将之改为后序遍历。每一层的语义变为“在已知当前分支序列最大值是last的情况下，第i位置后面还可以追加几个元素到序列中？”这样下钻到分支的叶子节点时，后面没有元素可供添加，直接返回0即可。然后在后序位置把计数 + 1，参见下方高亮代码：
const solveAsc = (i: number, queue: number[]): number => {
// 1. 越界检查
if (i === students.length) return 0;
// 2. 选择 A：跳过 students[i]
let max = solveAsc(i + 1, [...queue]);
// 3. 选择 B：包含 students[i]（如果合法）
const last = queue[queue.length - 1];
if (queue.length === 0 || students[i] > last) {
const m = solveAsc(i + 1, [...queue, students[i]]) + 1;
max = Math.max(max, m);
}
return max;
};现在可以改queue为last了，进一步优化为：
const solveAsc = (i: number, last: number): number => {
// 1. 越界检查放最前面
if (i === students.length) return 0;
// 2. 选择 A：跳过 students[i]
let max = solveAsc(i + 1, last);
if (students[i] > last) {
const m = solveAsc(i + 1, students[i]) + 1;
max = Math.max(max, m);
}
return max;
};当然别忘了添加缓存。递归版本的缓存非常好添加，因为状态就是参数，因此把参数序列化为缓存的key即可：
const memo = new Map<string, number>();
const solveAsc = (i: number, last: number): number => {
// 1. 越界检查放最前面
if (i === students.length) return 0;
const key = `${i},${last}`;
if (memo.has(key)) return memo.get(key)!;
// 2. 选择 A：跳过 students[i]
let max = solveAsc(i + 1, last);
if (students[i] > last) {
const m = solveAsc(i + 1, students[i]) + 1;
max = Math.max(max, m);
}
memo.set(key, max);
return max;
};到这里已经足够通过常规 case 了。当然我们也可以将其直接改写为 DP 版本：
| 递归 | 迭代 |
|---|---|
solveAsc(i, last) | dp[i][last] |
if (i === n) return 0; | dp[n][*] = 0 |
1 + solveAsc(i + 1, students[i]) | 1 + dp[i+1][students[i]] |
遍历方向怎么确定呢？取决于依赖方向，last有大小顺序，从0到题目给定的人群身高最大值maxValue（没给就用 case 的最大值），i则是dp[i]依赖dp[i+1]，先知道dp[n][*] = 0才能一层层上浮，所以需要倒过来：
const n = students.length;
const MAX_HEIGHT = Math.max(...students); // 用实际最大值
const fill = <T>(length: number, factory: () => T) => Array.from({ length }, factory);
const solveAsc = () => {
// last 列的下标 0 = 哨兵(-1)，不然最后 dp[0][-1] 取不到结果
const dp = fill(n + 1, () => fill(MAX_HEIGHT + 2, () => 0))
for (let i = n - 1; i >= 0; i--) {
for (let last = -1; last <= MAX_HEIGHT; last++) {
const li = last + 1; // 下标偏移
// 跳过
dp[i][li] = dp[i + 1][li];
// 选
if (students[i] > last) {
const si = students[i] + 1; // 身高也跟着偏移
dp[i][li] = Math.max(dp[i][li], 1 + dp[i + 1][si]);
}
}
}
// last = -1（还没选过任何人）→ 下标 0
return dp[0][0];
};合唱队形
完了没？还没完……如果题目摇身一变，要求给出“以每个位置结尾的递增子序列长度”，比如递增子序列问题的变体，“合唱队形”问题：要求找出形成左递增右递减的合唱队形，我们这个解法会遇到困难。因为我们的状态表中，第1列表示的是各位置处往后看最长递增子序列的长度，但不一定就是以当前位置值作为子序列开头，而想要解决合唱队形问题我们需要求得在从左至右/从右至左方向上，恰恰以该位置值作为峰值的递增/减子序列长度，如果当前位置不在子序列中就没法保证是峰值。
那就从头开始吧，合唱队形的解法描述已经给了我们指示，现在位置i处的元素就是代表序列最值的last，因此状态维度反而降了。还需要区分“选中”和“不选”吗，不需要也不可能需要了，毕竟现在明确i要被子序列选中。因此现在要反过来往前看，需要找到此前那些分支中，能够以当前位置结尾的子序列中最长的一个。
先写出递归版本：
const solveAsc = (i: number) => {
if (i === 0) return 1;
if(memo.has(i)) return memo.get(i)!;
let max = 1; // ← 初始值 1（代表"只选自己"）
for (let j = i - 1; j >= 0; --j) {
if (students[j] < students[i]) { // s[j] 比 s[i] 大，以s[j]结尾的队列不可能再追加s[i]
max = Math.max(1 + solveAsc(j), max);
}
}
memo.set(i, max);
return max;
};同样的，改写为DP迭代，现在状态只有一个i，只需要一维数组dp。遍历的方向上，solve(i)依赖solve(i-1)，故i需要正向，而j随意，毕竟dp[j < i]都算好了：
const solveAsc = () => {
const dp = fill(students.length, () => 0);
for (let i = 0; i < students.length; ++i) {
let max = 1;
for (let j = i - 1; j >= 0; --j) {
if (students[j] < students[i]) {
max = Math.max(1 + dp[j], max);
}
}
dp[i] = max;
}
return dp;
}有意思的是这才是经典的LIS解法，而且比我们一开始的解法更优，它只需要再对dp做一次max就可以求得整体最长子序列的长度，虽然时间复杂度一个是
回到合唱队形问题，只需要：
left[i] = 以 i 结尾的 LIS（经典定义）
right[i] = 以 i 开头的 LDS（经典定义的反向）
合唱人数 = left[i] + right[i] - 1
答案 = max(left[i] + right[i] - 1) ← 对所有 i 扫一遍