动态规划：两个数组的 DP 问题二

在动态规划问题中，涉及两个数组的问题通常有一些特定的规律或约束，可能是 子序列问题、子集问题，或 字符串匹配问题 等。

假设我们有两个数组，要求通过某种方式对它们进行比对、匹配或优化，这样的问题通常可以通过二维 动态规划表 来求解。下面将展示一个典型的“两个数组”类型的动态规划问题，并给出详细的解析和解法。

问题：最长公共子序列（LCS）

问题描述：

给定两个数组或字符串 A 和 B，求这两个数组的 最长公共子序列（LCS）。即，求在两个数组中都存在的最长子序列。

子序列是指在数组中删除一些元素（可以不删除任何元素），但不改变元素的顺序。

输入：

  • 数组 A 和数组 B
    • A = [1, 3, 4, 1]
    • B = [1, 2, 3, 4, 1]

输出：

  • LCS 的长度

例如，在上面的示例中，LCS 是 [1, 3, 4, 1]，长度为 4。

1. 动态规划解法

1.1. 状态定义

我们使用 二维 DP 表 来解决这个问题，dp[i][j] 表示 A[0...i-1] 和 B[0...j-1] 之间的最长公共子序列的长度。

1.2. 状态转移方程

  • 当 A[i-1] == B[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1。
    • 这意味着我们找到了一个公共元素，可以将它加入当前的子序列，且子序列长度增加1。
  • 当 A[i-1] != B[j-1] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
    • 如果当前的元素不相等，我们只能选择忽略 A[i-1] 或忽略 B[j-1]，因此选择这两者中的最大值。

1.3. 初始化

  • dp[i][0] = 0：表示空数组与任何数组的公共子序列长度为 0。
  • dp[0][j] = 0：表示任何数组与空数组的公共子序列长度为 0。

1.4. 算法实现

def longestCommonSubsequence(A, B):
    # 获取两个数组的长度
    m, n = len(A), len(B)
    
    # 创建二维 DP 表，初始化为 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充 DP 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 如果元素相同
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 如果元素不同
    
    # 最后一个单元格即为结果，表示最长公共子序列的长度
    return dp[m][n]

# 示例
A = [1, 3, 4, 1]
B = [1, 2, 3, 4, 1]
print(longestCommonSubsequence(A, B))  # 输出 4

1.5. 代码解释

  1. 初始化 DP 表：使用二维列表 dp 存储子问题的解，dp[i][j] 表示 A[0...i-1] 和 B[0...j-1] 之间的 LCS 长度。
  2. 状态转移：
    • 如果 A[i-1] == B[j-1]，说明这两个元素属于 LCS，dp[i][j] 的值为 dp[i-1][j-1] + 1。
    • 否则，LCS 的长度是 dp[i-1][j] 和 dp[i][j-1] 中的最大值。
  3. 最终结果：dp[m][n] 就是 A 和 B 之间的 LCS 长度。

1.6. 时间复杂度与空间复杂度

  • 时间复杂度：O(m * n)，其中 m 和 n 分别是数组 A 和数组 B 的长度。每个元素的计算都需要 O(1) 的时间，最终填充一个 m * n 的 DP 表。
  • 空间复杂度：O(m * n)，需要存储 m * n 的 DP 表。

2. 优化空间

我们可以通过观察到的规律，减少 dp 表的空间复杂度。从上面的递推关系来看，计算 dp[i][j] 只依赖于 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，因此只需要保存 当前行 和 前一行 即可。

优化空间的实现

def longestCommonSubsequence(A, B):
    m, n = len(A), len(B)
    
    # 初始化前一行和当前行
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    # 填充 DP 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr[:]  # 更新前一行

    return curr[n]

# 示例
A = [1, 3, 4, 1]
B = [1, 2, 3, 4, 1]
print(longestCommonSubsequence(A, B))  # 输出 4

2.1. 代码解释

  • 我们只维护 当前行 (curr) 和 前一行 (prev)，每次计算完一行后，将当前行赋值给前一行，减少空间消耗。

2.2. 时间与空间复杂度

  • 时间复杂度：依然是 O(m * n)，因为每个元素依然需要计算。
  • 空间复杂度：优化后是 O(n)，只需要存储 n + 1 的两行数组。

3. 总结

通过动态规划解决 两个数组的 LCS 问题，我们可以高效地计算出两个数组之间的最长公共子序列。关键的步骤是定义好状态转移方程，并通过二维数组存储子问题的解，最终求解出整个问题的答案。

  • 在本例中，使用 dp[i][j] 表示 A[0...i-1] 和 B[0...j-1] 的最长公共子序列长度。
  • 空间优化可以通过保存两行来进一步减少空间复杂度。

这种类型的 两个数组的动态规划问题 不仅是 LCS，类似的应用还有最长公共子串、编辑距离等问题，思路和技巧都非常相似。