最长公共子序列

最长公共子序列(LCS)是指两个序列中都出现过的最长的子序列。换句话说，通过删除一些元素后，剩下的最长公共子序列的长度。动态规划是解决LCS问题的一种有效方法。

动态规划方法

  1. 定义状态 ：
  • 设 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
  1. 状态转移方程 ：

  • 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。

  • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

  1. 初始化 ：

  • dp[j] = 0，表示 text1 为空时，最长公共子序列长度为0。

  • dp[i] = 0，表示 text2 为空时，最长公共子序列长度为0。

  1. 计算顺序 ：
  • 从 dp 开始，依次计算 dp[i][j] 的值，直到 dp[m][n]。
  1. 结果 ：
  • dp[m][n] 即为 text1 和 text2 的最长公共子序列的长度。

示例

假设 text1 = "abcde"，text2 = "ace"：

  1. 初始化 dp 数组：
    dp = 0
    dp = 0
    dp = 0
    dp = 1
    dp = 0
    dp = 1
    dp = 0
    dp = 1
    dp = 0
    dp = 2
    dp = 0
    dp = 2
    ```

2. 最终结果 `dp = 2`，即最长公共子序列的长度为2，最长公共子序列为 `"ace"`<b class="card40_249__sup_a7f6" data-sup="sup">1</b>。

### 优化空间复杂度<b class="card40_249__sup_a7f6" data-sup="sup">4</b>

由于 `dp[i][j]` 只依赖于 `dp[i-1][j-1]`、`dp[i-1][j]` 和 `dp[i][j-1]`，可以使用一维数组来优化空间复杂度<b class="card40_249__sup_a7f6" data-sup="sup">1</b>。

### 代码实现

```python
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [ * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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]

总结

最长公共子序列问题是一个经典的动态规划问题，通过构建 dp 数组并利用状态转移方程，可以高效地求解两个字符串的最长公共子序列的长度。

Top
×
×