算法

最近面试复习，发现已经完全失去了写 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];
};

TIP

带缓存的递归和迭代版本性能上并不完全等价。关键在于，迭代要求状态下标必须是线性的，而递归可以精准地跳到下一个有效状态，自带剪枝。以这个题目为例，由于队伍人数有限，大概率所有人的身高不会均匀填满 0 到 MAX_HEIGHT 之间的每一个值，而递归版本可以精准地从一个 h1 跳到下一个 h2，省去了从 h1 遍历到 h2 的过程。

合唱队形

完了没？还没完……如果题目摇身一变，要求给出“以每个位置结尾的递增子序列长度”，比如递增子序列问题的变体，“合唱队形”问题：要求找出形成左递增右递减的合唱队形，我们这个解法会遇到困难。因为我们的状态表中，第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就可以求得整体最长子序列的长度，虽然时间复杂度一个是$O(n^2)$一个是$O(n\ast range)$量级相同，但空间复杂度$O(n)$无疑比我们的二维状态$O(n^2)$要好得多。

回到合唱队形问题，只需要：

left[i]  = 以 i 结尾的 LIS（经典定义）
right[i] = 以 i 开头的 LDS（经典定义的反向）

合唱人数 = left[i] + right[i] - 1
答案     = max(left[i] + right[i] - 1)  ← 对所有 i 扫一遍

最小编辑距离

做这题的时候思路异常清晰……如果真的去操作字符串，一个下标要考虑左（左侧插入）、中（替换当前）和右（右侧删除）三个位置的变更，光是想想就非常麻烦。实际上只需要定义两个指针i和j，分别指向s串和t串当前在比对的位置，以i为基准和j对齐，如果s[i] !== s[j]，则按 i-1和j、i+1和j+1、i+1和j 左中右三种情况取最小者，不需要真的操作字符串，直接视下标左侧的串已相等，往右侧考虑：

const solve = (i: number, j: number) => {
  if (i === s.length) return t.length - j; // 一个串已消耗完，剩下的都需要追加
  if (j === t.length) return s.length - i;

  const key = `${i},${j}`;

  if (memo.has(key)) return memo.get(key);

  let min = solve(i + 1, j + 1);
  if (s[i] !== t[j]) {
    min =
      1 +
      Math.min(
        solve(i, j + 1), // insert at i
        solve(i + 1, j), // delete i
        min // replace i
      );
  }

  memo.set(key, min);

  return min;
};

转换为DP形态，主要思考遍历方向，递归过程中solve(i, j)都依赖后续的solve(i+1, j+1)等状态，所以遍历时要倒过来：

const solveDP = () => {
  const dp = fill(s.length + 1, () => fill(t.length + 1, () => 0));

  for (let i = 0; i < s.length + 1; ++i) {
    dp[i][t.length] = s.length - i;
  }
  for (let j = 0; j < t.length + 1; ++j) {
    dp[s.length][j] = t.length - j;
  }

  for (let i = s.length - 1; i >= 0; --i) {
    for (let j = t.length - 1; j >= 0; --j) {
      let min = dp[i + 1][j + 1];

      if (s[i] !== t[j]) {
        min = 1 + Math.min(
          dp[i][j + 1],
          dp[i + 1][j],
          min
        );
      }

      dp[i][j] = min;
    }
  }

  dp.forEach(x => console.log(x));
  return dp[0][0];
}

回溯

印象中我们以前的算法教材，回溯是放在动态规划前面讲的。但说实话我心里面对回溯总觉得毛毛的，理由是回溯的那个choices，有时相比起动态规划的子问题更难找准，没法在一开始就枚举完毕，而是要在遍历的时候动态展开。

// 找所有解
const backtrace = (choices, state, path) => {
  if (condition(choices, path)) {
    result.push([...path]);
    return;
  }

  for (const choice of choices) {
    // choose
    path.push(choice);

    backtrace(choices, newState(state), path);

    // unchoose
    path.pop();
  }
};

全排列和子集

先来看看经典的全排列问题。递归代表下钻，而中间的迭代代表水平遍历子节点，这是典型的DFS，只不过我们没有在先序或后序位置收集状态，而是在叶子处直接收集结果。这里为了书写方便我把树横置了：

• root: choices = [1,2,3], path = []
  • i=0: choices = [2,3], path = [1]
    • i=0: choices = [3], path = [1,2]
      • i=0: choices = [], path = [1,2,3]
    • i=1: choices = [2], path = [1,3]
      • i=0: choices = [], path = [1,3,2]
  • i=1: choices = [1,3], path = [2]

const result: number[][] = [];

const solve = (choices: number[], path: number[]) => {
  if (choices.length === 0) {
    result.push(path);
    return;
  }

  for (let i = 0; i < choices.length; ++i) {
    const x = choices[i];

    // choose
    path.push(x);
    choices.splice(i, 1);

    solve(choices, [...path])

    // unchoose
    path.pop();
    choices.splice(i, 0, x);
  }
}

此处没有用上额外的状态state，是因为直接调整choices足够完成状态枚举。当然这样频繁分配数组不是好习惯，更多时候会引入一个额外的visited状态取代 loop 里的splice过程，同时此时condition不能再用choices.length === 0来判断，改用visited.size或path.length判断：

const solve = (choices: number[], visited: Set<number>, path: number[]) => {
  if (choices.length === visited.size) {
    result.push([...path]);
    return;
  }

  for (let i = 0; i < choices.length; ++i) {
    if (visited.has(i)) continue;
    const x = choices[i];

    // choose
    path.push(x);
    visited.add(i);

    solve(choices, visited, path)

    // unchoose
    path.pop();
    visited.delete(i);
  }
}

将全排列的算法改一改，在中途每一个节点上收集结果，就得到了求全部子集问题的算法：

const solve = (choices: number[], visited: Set<number>, path: number[]) => {
  for (let i = 0; i < choices.length; ++i) {
    if (visited.has(i)) continue;
    const x = choices[i];

    // choose
    path.push(x);
    visited.add(i);
    result.push([...path]);

    solve(choices, visited, path)

    // unchoose
    path.pop();
    visited.delete(i)
  }
}

但是这个算法会引入重复的子集，比如第一层i=0和第二层i=1收集到[1,2]，第一层i=1和第二层i=0收集到[2,1]，实际第一层i=1时，下钻第二层不应该再从0开始，而是从当前位置开始往后遍历。因此再引入一个状态，记录当前的startIndex：

const solve = (choices: number[], visited: Set<number>, startIndex: number, path: number[]) => {
  for (let i = startIndex; i < choices.length; ++i) {
    if (visited.has(i)) continue;
    const x = choices[i];

    // choose
    path.push(x);
    visited.add(i);
    result.push([...path]);

    solve(choices, visited, i, path)

    // unchoose
    path.pop();
    visited.delete(i)
  }
}

数独

把所有是0（0代表空白待填）的位置收集起来充当选项很容易想到，但是每个位置上可以填 1~9 个数字，所以是不是得用空格数量和 9 个数字做笛卡尔积充当choices呢，这样可以求解。但还有个更优雅的思路，额外增加一个状态zIndex，在竖直（下钻）方向上进行空白位置的遍历，在水平（子节点）方向上进行 1~9 的穷举：

数独的例子提示我们可以自由控制横向和纵向展开的内容。

const solve = (m: number[][], zeros: number[][], zIndex: number) => {
  if (zIndex === zeros.length) return true;

  for (let n = 1; n < 10; ++n) {
    const p = zeros[zIndex];
    if (!isValidPosition(n, p)) continue;
    
    // choose
    m[p[0]][p[1]] = n;

    if (solve(m, zeros, zIndex + 1)) return true;

    // unchoose
    m[p[0]][p[1]] = 0;
  }

  return false;
};