1143. 最长公共子序列 -- 动规

1143. 最长公共子序列

class LongestCommonSubsequence2:
    """
    1143. 最长公共子序列
    https://leetcode.cn/problems/longest-common-subsequence/
    """
    def solution(self, text1: str, text2: str) -> int:
        """
        递归解法 + 备忘录
        自顶向下
        :param text1:
        :param text2:
        :return:
        """
        m, n = len(text1), len(text2)
        self.memo = [[-1 for _ in range(n)] for _ in range(m)]

        return self.dp(text1, 0, text2, 0)

    def dp(self, text1, i, text2, j):
        """
        计算text1[i..] 和 text2[j..]的子序列长度
        :param text1:
        :param i:
        :param text2:
        :param j:
        :return:
        """
        # base case
        if i == len(text1) or j == len(text2):
            return 0
        # 备忘录
        if self.memo[i][j] != -1:
            return self.memo[i][j]

        if text1[i] == text2[j]:
            self.memo[i][j] = 1 + self.dp(text1, i+1, text2, j+1)
        else:
            self.memo[i][j] = max(self.dp(text1, i + 1, text2, j),
                                  self.dp(text1, i, text2, j + 1))

        return self.memo[i][j]

    @classmethod
    def solution2(cls, text1: str, text2: str) -> int:
        """
        自底向上
        迭代 动规
        :param text1:
        :param text2:
        :return:
        """
        m, n = len(text1), len(text2)
        # dp[m][n] 表示 text1[0..m-1][0..n-1]的lcs
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

        # base case
        # dp[0][...]   dp[...][0] = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

        return dp[m][n]

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67