【算法】【Python】使用动态规划（DP）解决最长公共子序列（LCS）问题

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    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]:  # 当前字符匹配
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 取两种情况的最大值
    print("打印DP数组：")
    for i in dp:
        print(i)

    # 回溯找出LCS字符串
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:  # 相同字符，加入 LCS
            lcs.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:  # 来自上方
            i -= 1
        else:  # 来自左方
            j -= 1
    
    print("".join(reversed(lcs)))  # 反转得到正确顺序的 LCS
    return dp[m][n]

# 测试
text1 = "aefegd"
text2 = "baed"
print(longest_common_subsequence(text1, text2))  # 输出: 3 ("ace")

打印DP数组：
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 0, 1, 2, 2]
[0, 0, 1, 2, 2]
[0, 0, 1, 2, 2]
[0, 0, 1, 2, 2]
[0, 0, 1, 2, 3]
aed
3

思路就是用一个二维的dp数组来存储子问题的解，dp[i][j]则表示文本1从0到i和文本2从0到j的最长公共子序列的长度。如果text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1（左上角位置值+1），否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])（左边和上边的最大值）。回溯同理，如果当前行列对应的字符相等，就加到字符串中，不相等就找左边和上边哪个大，往大的方向走，一直循环。