【算法深入理解】[动态规划]最长公共子序列

一个问题具有最优子结构，且每一个解也是最优的，那么求得的即是最优解。

动态规划只适用于具有最优子结构的问题。而最优子结构表示的是局部的最优解可以决定全局的最优解，而更简单的说法即是： 问题可以分成更小的小问题 。听起来跟分治法有些类似，这里做一个简单的区分：

分治法主要是将原问题划分成一个个独立的子问题，递归地对子问题进行求解之后，将每个子问题的结果进行合并而得到原问题的解。主要步骤是：

1. 分解
2. 解决
3. 合并

动态规划与分治法不同，动态规划适用于子问题独立且重叠的问题，重叠的意义在于每个子问题都包含一部分相同的子子问题，动态规划会对这些子子问题求解且只求解一次并且保存在表中，当需要使用到公共部分时直接从表中取而避免重复计算。

动态规划中包含两个主要要素：

1. 最优子结构
2. 重叠子问题

最优子结构：如果一个问题的最优解包含了其子问题的最优解，那么该问题具有最优子结构。

重叠子问题：在两个不同的子问题中，如果他们是相同的子问题，只是作为不同问题的子问题提出时，他们是重叠的。且动态规划中对于重叠的子问题不再重复计算，而是从固定空间中取出之前已经求得的子问题解。

动态规划求解步骤：

1. 划分最优化问题，找出最优解性质，刻画其结构特性
2. 构造状态表示，确定递推/递归关系，确定边界条件
3. 按自底向上的方式计算最优解的值

若需要求得最优解，则需要根据计算结果的表格来构造最优解。

LCS(Longest Common Subsequence)问题

问题描述

如果一个序列Seq1按照其字母出现的顺序出现在另一个序列Seq2上，那么称该序列Seq1为另一个序列Seq2的子序列。

PS：Seq1中的字母并不需要连续的出现在Seq2中。

问题：给出两个序列，要求求出它们的最长公共子序列。

例如：给出序列 Seq1: abcbdab 和 序列 Seq2: bdcaba ， 其最长公共子序列为： bcab （不唯一，给出一个即可）

求解思路

1. 刻画最优子结构

假设 $X_i$ 表示序列 $X$ 的前 $i$ 个字母组成的子序列，$Y_j$ 表示序列 $Y$ 的前 $j$ 个字母组成的子序列。且 $Z$ 为 $X, Y$ 的最长公共子序列。$x_i$ 表示序列 $X$ 的第 $i$ 个字符，$y_j$ 表示序列 $Y$ 的第 $j$ 个字符。$k$ 为 $Z$ 的长度。

限制条件：$i<=m, j<=n$（其中 $m$ 是 $X$ 的长度，$n$ 是 $Y$ 的长度）

那么有如下几种情况：

• 如果 $x_m=y_n$，那么两个序列的最后一个字符一定是最长公共子序列 $Z$ 的最后一个字符，即 $x_m=y_n=z_k$。此时已经确定最后一个字符，那么问题化归为求解 $Z_{k-1}$，且 $Z_{k-1}\in LCS(X_{m-1},Y_{n-1})$。此时 $Z_{k-1}$ 是 $X_{m-1}, Y_{n-1}$ 的公共最长子序列。

• 如果 $x_m \ne y_n$，那么要么 $Z \in LCS(X_{m-1}, Y)$，要么 $Z \in LCS(X, Y_{n-1})$，问题化归为求解 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$。

由于第二点中 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$ 不相互独立，都需要求解 $LCS(X_{m-1}, Y_{n-1})$，具有 最优子结构 性质，故使用动态规划法求解。

2. 确定递推/递归关系式

由最优子结构性质可知，若要求 $X,Y$ 的最长公共子序列，则按如下方式进行递推式求解：

当 $x_m=y_n$，$LCS(X,Y)$ 就是 $LCS(X_{m-1}, Y_{n-1})$ 再在尾部加上 $x_m$ 或 $y_n$。

当 $x_m \ne y_n$，那么要解决两个子问题，即找出 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$，且其中更长的为 $LCS(X,Y)$，即 $Max(LCS(X_{m-1}, Y),LCS(X, Y_{n-1}))$

由此递推结构容易看到最长公共子序列问题具有子问题重叠性质，都需要求解 $LCS(X_{m-1}, Y_{n-1})$。

利用 $record[i][j]$ 来记录 $X_i, Y_j$ 的最长公共子序列的长度。

边界条件：当 $i$ 或 $j$ 为 $0$ 时，空序列是 $X, Y$ 的最长子序列，即 $record[i][j] = 0$，其他递推关系如下：

3. 求解最优值

根据上面给出的递推关系以及边界条件，很容易写出相关代码：

function LCS(str1 = '', str2 = '') {
  if (!str1 || !str2) {
    return 0;
  }

  const len1 = str1.length;
  const len2 = str2.length;

  if (!len1 || !len2) {
    return 0;
  }

  // LCS 长度记录
  let record = new Array(len1 + 1).fill([]).map(k => []);

  // 初始化 记录表
  for (let i = 0; i <= len1; i++) {
    record[i][0] = 0;
  }

  for (let j = 0; j <= len2; j++) {
    record[0][j] = 0;
  }

  // 自底向上求解
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      let ch1 = str1.charAt(i - 1);
      let ch2 = str2.charAt(j - 1);

      if (ch1 === ch2) {
        record[i][j] = record[i - 1][j - 1] + 1;
      } else if (record[i - 1][j] >= record[i][j - 1]) {
        record[i][j] = record[i - 1][j]
      } else {
        record[i][j] = record[i][j - 1]
      }
    }
  }

  console.log(`Length: ${record[len1][len2]}`);
}

以上算法的时间复杂度为 $O(mn)$