[动态规划]Leetcode 1143.最长公共子序列(python)

题目描述

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

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

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

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

示例1

输入：text1 = “abcde”, text2 = “ace”

输出：3

解释：最长公共子序列是 “ace”，它的长度为 3。

示例2

输入：text1 = “abc”, text2 = “abc”

输出：3

解释：最长公共子序列是 “abc”，它的长度为 3。

提示:

1 <= text1.length <= 1000

1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

DP定义及状态方程

一般来说对于两个字符串类型的长度问题，都会定义一个dp[i][j]代表字符串s1[1...i]与s2[1...j]所求的问题。对于本题同样定义

dp[i][j]表示s1[1...i]和s2[1...j]的最长公共子序列为dp[i][j]。

递推方程

1. 那么当s1[i-1]==s2[i-1]时，dp[i][j]的最长公共子序列是在dp[i-1][j-1]的基础上加1，即dp[i][j]=dp[i-1][j-1]+1;

2. 当s1[i-1]！=s2[i-1]时，dp[i][j]的最长公共子序列为max(dp[i][j-1], d[i-1][j])

3. 本题的目标值即为dp[len(s1)-1][len(s2)-1]

dp数组结构 如下图所示：

初始边界条件

对于s1[0]对应的s2[j]均为0，即dp[0][j]=0，0=< j< len(s2);

同理 dp[i][0]=0,0 =< i < len(s1)

最终代码如下

# 动态规划，dp数组形式求解
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0] * (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][j-1],dp[i-1][j])
        return dp[-1][-1] #dp的最后一个数即为本题答案

附上递归形式的写法，思想其实与dp数组求解形式相同，只是需要用备忘录memo记录已经求解过的值，防止重复计算。

#递归的形式求解
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 递归
        memo = {} #备忘录
        def dp(i, j):
            if i == -1 or j == -1:
                return 0
            if (i,j) in memo:
                return memo[(i,j)]
            if text1[i] == text2[j]:
                memo[(i,j)] = dp(i-1, j-1) + 1
            else:
                memo[(i,j)] = max(dp(i-1, j), dp(i,j-1))
            return memo[(i,j)]
        return dp(len(text1)-1,len(text2)-1)