代码收藏家技术教程 2025-02-10

【算法】动态规划专题④ ——LCS（最长公共子序列）+ LPS（最长回文子序列） python

前置知识

【算法】动态规划专题③ ——二维DP python

子序列定义为：
不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

LCS

最长公共子序列 https://www.lanqiao.cn/problems/1189/learning/?page=1&first_category_id=1&problem_id=1189

题目描述

给定一个长度为N数组a和一个长度为M的数组b。请
你求出它们的最长公共子序列长度为多少。

输入描述
输入第一行包含两个整数N,M,分别表示数组a和b的长度。
第二行包含N个整数a1,a2,…,an。
第三行包含M个整数b1,b2,…,bm

输出描述
输出一行整数表示答案。

1≤N,M≤1e3,1≤ai,bi≤1e9

思路：

定义dp[i][j]表示序列A的前i个元素和序列B的前j个元素之间的最长公共子序列的长度。
当 A[i-1] = B[j-1]，在这种情况下，dp[i][j] = dp[i-1][j-1] + 1
当 A[i-1] != B[j-1]，我们需要决定去掉 A[i]或者B[i]来寻找更大值
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这里，dp[i-1][j]表示不包括A的第i个元素的最大LCS长度，而dp[i][j-1]表示不包括B的第j个元素的最大LCS长度

代码如下：

n, m = map(int, input().split())
a =list(map(int, input().split()))
b =list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 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])

print(dp[n][m])

通过路径回溯可以重建出具体的LCS

举一反三

两个字符串的删除操作 https://leetcode.cn/problems/delete-operation-for-two-strings/description/

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea” ，第二步将 "eat "变为 “ea”

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

思路：

计算 两个字符串的长度 和 最长公共子序列的长度之差即可

题解code：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[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 n + m - dp[n][m] * 2

LPS

最长回文子序列 https://leetcode.cn/problems/longest-palindromic-subsequence/description/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路：

LPS转化为LCS
将s和逆序的s做最长公共子序列即可得到最长回文子序列

code：

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        ss = s[::-1]
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == ss[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[n][n]