动态规划-最长公共子序列

题目

最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。
示例 2:

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。
示例 3:

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:

1 <= text1.length <= 1000
1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

思路

状态表示

我们可以使用动态规划（Dynamic Programming, DP）来解决这个问题。具体来说，我们使用一个二维数组 dp[i][j] 来表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。

  • dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。

状态计算

dp
在这里插入图片描述
\

四种情况分析

让我们详细分析这四种情况，以及它们如何影响 dp[i][j] 的值：

1. 00（不包含 text1[i-1] 和 text2[j-1]）

这意味着我们在计算 dp[i][j] 时既不包含 text1[i-1] 也不包含 text2[j-1]，即我们从 dp[i-1][j-1] 继承。

但这里需要注意的是，这种情况实际上是“隐式”包含在下面两种情况中的，因此我们不需要单独列出：

  • 情况 1: 如果 text1[i-1] != text2[j-1]，则最长公共子序列不会包括 text1[i-1] 或 text2[j-1]，我们需要从两个方向选择一个较大的值，表示我们“跳过”了这两个字符，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
2. 01（不包含 text1[i-1]，包含 text2[j-1]）
  • 情况 2: 如果我们不考虑 text1[i-1]，但考虑 text2[j-1]，则 dp[i][j] = dp[i][j-1]，即我们不包括 text1[i-1]，但可能从 dp[i][j-1] 中获得结果。
3. 10（包含 text1[i-1]，不包含 text2[j-1]）
  • 情况 3: 如果我们不考虑 text2[j-1]，但考虑 text1[i-1]，则 dp[i][j] = dp[i-1][j]，即我们不包括 text2[j-1]，但可能从 dp[i-1][j] 中获得结果。
4. 11（包含 text1[i-1] 和 text2[j-1]）
  • 情况 4: 如果 text1[i-1] == text2[j-1]，那么我们可以同时包含 text1[i-1] 和 text2[j-1]，此时 dp[i][j] = dp[i-1][j-1] + 1。

合并这些情况

综合这些情况，我们可以得出状态转移方程：

  • 如果 text1[i-1] == text2[j-1]，则：
    d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1] + 1 dp[i][j]=dp[i−1][j−1]+1
  • 如果 text1[i-1] != text2[j-1]，则：
    d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) dp[i][j]=max(dp[i−1][j],dp[i][j−1])

状态转移的总结

我们不需要显式地处理 00 这种情况，因为它已经包含在 01 和 10 中。当字符不相等时，我们从 dp[i-1][j] 和 dp[i][j-1] 中选取最大值，表示我们跳过了某个字符。

例子

考虑以下示例，text1 = "abcde" 和 text2 = "ace"：

“”ace
“”0000
a0111
b0111
c0122
d0122
e0123
  • dp[1][1] = 1，表示 "a" 和 "a" 匹配，公共子序列长度为 1。
  • dp[2][2] = 1，表示 "b" 和 "c" 不匹配，最长公共子序列仍然是之前的 "a"。
  • dp[3][3] = 2，表示 "c" 和 "e" 匹配，公共子序列变为 "ac"。
  • 最终的 dp[5][3] = 3，表示 "abcde" 和 "ace" 的最长公共子序列长度为 3，子序列为 "ace"。
    在这里插入图片描述

DP 数组的初始化

DP 数组 dp[i][j] 的定义是：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。

初始化步骤

  1. 当 text1 或 text2 中有一个字符串为空时，显然其与另一个字符串的公共子序列的长度为 0。因此，所有的 dp[0][j] 和 dp[i][0] 都应该初始化为 0。

    • dp[0][j] = 0，表示当 text1 为空时，任何 text2 子串的最长公共子序列长度为 0。
    • dp[i][0] = 0，表示当 text2 为空时，任何 text1 子串的最长公共子序列长度为 0。

  2. 一般情况下，初始化二维 DP 数组的过程如下：

    • 创建一个大小为 (m+1) x (n+1) 的二维数组，其中 m 是 text1 的长度，n 是 text2 的长度。
    • 初始化 dp[0][j] 和 dp[i][0] 为 0。

代码实现

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    
    # 初始化 DP 数组，大小为 (m+1) x (n+1)
    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 text1[i - 1] == text2[j - 1]:
                # 如果字符相等，当前公共子序列的长度加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]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

代码解析

  1. 初始化 DP 数组：

    • 使用 dp = [[0] * (n + 1) for _ in range(m + 1)] 初始化了一个大小为 (m+1) x (n+1) 的二维数组，dp[i][j] 用来存储 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。
    • 初始化时，dp[i][0] 和 dp[0][j] 都被设置为 0，表示当任意一个字符串为空时，最长公共子序列的长度为 0。

  2. DP 填充过程：

    • 对于每一对字符 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])，表示我们要么跳过 text1[i-1]，要么跳过 text2[j-1]。

  3. 返回结果：

    • 最终的最长公共子序列的长度存储在 dp[m][n] 中，即 text1[0..m-1] 和 text2[0..n-1] 的最长公共子序列长度。

时间和空间复杂度

  • 时间复杂度：O(m * n)，我们需要遍历 text1 和 text2 的每一对字符，并更新 DP 表。
  • 空间复杂度：O(m * n)，我们使用了一个二维数组来存储所有子问题的解。

空间优化

如果只关心当前行和上一行的状态，我们可以优化空间复杂度，使用滚动数组（两个一维数组）代替二维数组，减少空间消耗。

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    
    # 初始化两个一维数组，分别用于存储上一行和当前行
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    # 填充 DP 数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        
        # 将当前行的结果存入上一行，准备计算下一行
        prev, curr = curr, prev
    
    # 返回最终结果
    return prev[n]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

好的！下面我将为你提供 Go 和 C++ 语言的代码实现，帮助你在这两种语言中解决 最长公共子序列（LCS）问题。

Go 语言实现

package main

import "fmt"

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    
    // 初始化一个二维数组 dp，用于存储子问题的结果
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    // 填充 dp 数组
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            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])  // 否则取最大值
            }
        }
    }
    
    // 返回最终的结果，dp[m][n] 就是最长公共子序列的长度
    return dp[m][n]
}

// 辅助函数：返回两个整数中的较大者
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    text1 := "abcde"
    text2 := "ace"
    fmt.Println(longestCommonSubsequence(text1, text2))  // 输出 3
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

C++ 语言实现

#include 
#include 
#include 
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    
    // 创建一个 (m+1) x (n+1) 的二维 dp 数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 填充 dp 数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;  // 如果字符相等，公共子序列长度加 1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  // 否则取最大值
            }
        }
    }
    
    // 返回最长公共子序列的长度
    return dp[m][n];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << longestCommonSubsequence(text1, text2) << endl;  // 输出 3
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

代码解释

  1. 初始化 DP 数组：
    在这两个实现中，我们都创建了一个二维数组 dp，dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。数组的尺寸为 (m+1) x (n+1)，m 和 n 分别是两个字符串的长度。dp[i][0] 和 dp[0][j] 都初始化为 0，表示当某个字符串为空时，最长公共子序列的长度为 0。

  2. 填充 DP 表：

    • 我们遍历每一对字符 text1[i-1] 和 text2[j-1]，如果这两个字符相等，那么公共子序列的长度是 dp[i-1][j-1] + 1，否则取 dp[i-1][j] 和 dp[i][j-1] 的最大值，表示我们跳过了其中一个字符。

  3. 返回结果：
    最终，dp[m][n] 存储的就是 text1 和 text2 的最长公共子序列的长度。

Go 语言优化版：
package main

import "fmt"

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    
    // 保留上一行和当前行的数组
    prev := make([]int, n+1)
    curr := make([]int, n+1)
    
    // 填充 DP 数组
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                curr[j] = prev[j-1] + 1
            } else {
                curr[j] = max(prev[j], curr[j-1])
            }
        }
        prev, curr = curr, prev  // 切换当前行和上一行
    }
    
    return prev[n]  // 返回结果
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    text1 := "abcde"
    text2 := "ace"
    fmt.Println(longestCommonSubsequence(text1, text2))  // 输出 3
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
C++ 语言优化版：
#include 
#include 
#include 
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    
    // 初始化两行数组
    vector<int> prev(n + 1, 0), curr(n + 1, 0);
    
    // 填充 DP 数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = max(prev[j], curr[j - 1]);
            }
        }
        prev = curr;  // 切换当前行和上一行
    }
    
    return prev[n];  // 返回结果
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << longestCommonSubsequence(text1, text2) << endl;  // 输出 3
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

参考

  1. acwingyxc老师
  2. 代码随想录
注：本文转载自blog.csdn.net的GGJOB的文章"https://blog.csdn.net/weixin_51147313/article/details/143886482"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！