【数据结构与算法】系列三十七 - 动态规划（最长公共子序列）

发表于 | 分类于
| 字数统计 1.7k 字 | 阅读时长 7 分钟

相信在上一章节你已经对动态规划有一定的深入了解，我们再通过几个高频算法面试题加深理解。

一、最长公共子序列

最长公共子序列（Longest Common Subsequence，简称 LCS）。

LeetCode：https://leetcode-cn.com/problems/longest-common-subsequence/

题目：求两个序列的最长公共子序列长度。

举例1：[1, 3, 5, 9, 10]和[1, 4, 9, 10]的最长公共子序列是[1, 9, 10]，长度为3。

举例2：ABCBDAB和BDCABA的最长公共子序列长度是4，可能的结果：

  • ABCBDAB 和 BDCABA > BDAB
  • ABCBDAB 和 BDCABA > BDAB
  • ABCBDAB 和 BDCABA > BCAB
  • ABCBDAB 和 BDCABA > BCBA

1.1. 思路

假设2个序列分别是nums1、nums2，i ∈ [1, nums1.length]，
j ∈ [1, nums2.length]，i和j代表长度。

1.1.1. 定义状态

假设dp(i, j)是【nums1前 i 个元素】与【nums2前 j 个元素】的最长公共子序列长度。

比如nums1 = {1, 3, 5, 9, 10}，nums2 = {1, 4, 9, 10}：

  • dp(2, 3)意思是nums1的前2个元素（{1, 3}）和nums2的前3个元素（{1, 4, 9}）的最长公共子序列长度，最长公共子序列是{1}，长度是1
  • dp(4, 4)意思是nums1的前4个元素（{1, 3, 5, 9}）和nums2的前4个元素（{1, 4, 9, 10}）的最长公共子序列长度，最长公共子序列是{1, 9}，长度是2

因此求两个数组的最长公共子序列就是求dp(nums1.length, nums2.length)的解。

1.1.2. 初始状态

dp(i, 0)、dp(0, j)初始值均为0。

1.1.3. 状态转义方程

前i个元素中，最后一个元素位置是i - 1；同理，前j个元素中，最后一个元素位置是j - 1，因此可以用下图表示他们的关系：

由上可知，我们只需要比较两个子序列的最后一个元素是否相等，即nums1[i – 1]和nums2[j – 1]是否相等。如果最后一个元素相等，只需要判断剩余的元素是否相等即可。如果最后一个元素不等，i和j反复交替进行-1（i--或j--）操作，如下图，最终取后面两图的最大值就是我们要求的最长公共子序列长度。

  • 如果nums1[i – 1] == nums2[j – 1]，那么dp(i, j) = dp(i – 1, j – 1) + 1
  • 如果nums1[i – 1] ≠ nums2[j – 1]，那么dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }

1.2. 实现

对比递归和动态规划，看一下两种实现方式的区别。

1.2.1. 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static int lcs(int[] nums1, int[] nums2) {
  if (nums1 == null || nums1.length == 0) return 0;
  if (nums2 == null || nums2.length == 0) return 0;
  return lcs(nums1, nums1.length, nums2, nums2.length);
}

/**
  * 求nums1前i个元素和nums2前j个元素的最长公共子序列长度
  * @param nums1
  * @param i
  * @param nums2
  * @param j
  */
private static int lcs(int[] nums1, int i, int[] nums2, int j) {
  if (i == 0 || j == 0) return 0;
  if (nums1[i - 1] == nums2[j - 1]) {
    return lcs1(nums1, i - 1, nums2, j - 1) + 1;
  }
  return Math.max(lcs1(nums1, i - 1, nums2, j), 
          lcs1(nums1, i, nums2, j - 1));
}

空间复杂度：$O(k)$，k = min {n, m}，n、m是2个序列的长度。因为i == 0或j == 0时，递归就结束了，所以空间复杂度看递归深度（函数在栈空间所在内存）。

时间复杂度：当 $n == m$ 时，$O(2^n)$ 。

1.2.2. 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static int lcs(int[] nums1, int[] nums2) {
  if (nums1 == null || nums1.length == 0) return 0;
  if (nums2 == null || nums2.length == 0) return 0;
  int[][] dp = new int[nums1.length + 1][nums2.length + 1];
  for (int i = 1; i <= nums1.length; i++) {
    for (int j = 1; j <= nums2.length; j++) {
      if (nums1[i - 1] == nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[nums1.length][nums2.length];
}

空间复杂度：$O(n*m)$

时间复杂度：$O(n*m)$

空间复杂度比递归还高，但时间复杂度明显减少，因此是典型的空间换时间。

1.2.2.1. 优化 - 滚动数组

假设序列1 = ABCBDAB，序列2 = BDCABA，j代表序列1的前j个元素，i代表序列2的前i个元素，dp数组（最长公共子序列长度）的计算结果如下所示：

从上图也可以看出：

  • 当i和j元素相等时，最长公共子序列长度是左上角的值加1，如图中紫色标注部分
  • 如果不相等，最长公共子序列长度是当前位置的左边（i - 1）和上边（j - 1）取最大值。

每一行的数据都是从当前行（左边）和上一行（左上角和上边）计算得来的，也就是说当计算第n行时，n - 1行前面的行数据其实是无用的（内存占用），因此我们可以使用滚动数组优化代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int lcs(int[] nums1, int[] nums2) {
  if (nums1 == null || nums1.length == 0) return 0;
  if (nums2 == null || nums2.length == 0) return 0;
  int[][] dp = new int[2][nums2.length + 1];
  for (int i = 1; i <= nums1.length; i++) {
    int row = i & 1;
    int prevRow = (i - 1) & 1;
    for (int j = 1; j <= nums2.length; j++) {
      if (nums1[i - 1] == nums2[j - 1]) {
        dp[row][j] = dp[prevRow][j - 1] + 1;
      } else {
        dp[row][j] = Math.max(dp[prevRow][j], dp[row][j - 1]);
      }
    }
  }
  return dp[nums1.length & 1][nums2.length];
}
1.2.2.2. 优化 - 一维数组

可以将二维数组优化成一维数组，进一步降低空间复杂度。

当两个字符不等时，当前位置dp(j)的值是上一个dp(j)位置的值和当前位置左边的值dp(j - 1)共同决定的（取最大值）。如果覆盖之前把dp(j)的值保留下来，这个值就是参与下一次计算的左上角值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int lcs(int[] nums1, int[] nums2) {
  if (nums1 == null || nums1.length == 0) return 0;
  if (nums2 == null || nums2.length == 0) return 0;
  int[] dp = new int[nums2.length + 1];
  for (int i = 1; i <= nums1.length; i++) {
    int cur = 0;
    for (int j = 1; j <= nums2.length; j++) {
      int leftTop = cur;
      cur = dp[j];
      if (nums1[i - 1] == nums2[j - 1]) {
        dp[j] = leftTop + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
    }
  }
  return dp[nums2.length];
}

减小dp数组长度，序列长度小的作为列，序列长度大的作为行。可以把空间复杂度优化至O(k)，k=min{n, m}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int lcs(int[] nums1, int[] nums2) {
  if (nums1 == null || nums1.length == 0) return 0;
  if (nums2 == null || nums2.length == 0) return 0;
  int[] rowsNums = nums1, colsNums = nums2;
  if (nums1.length < nums2.length) {
    colsNums = nums1;
    rowsNums = nums2;
  }
  int[] dp = new int[colsNums.length + 1];
  for (int i = 1; i <= rowsNums.length; i++) {
    int cur = 0;
    for (int j = 1; j <= colsNums.length; j++) {
      int leftTop = cur;
      cur = dp[j];
      if (rowsNums[i - 1] == colsNums[j - 1]) {
        dp[j] = leftTop + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
    }
  }
  return dp[colsNums.length];
}