带娃刷题第336天 动态规划算法 最长公共子串 LCS 由底到上递推

Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1, n2 = len(text1), len(text2)

        dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]

        for i in range(1, n1 + 1):
          for j in range(1, n2 + 1):
          if text1[i - 1] == text2[j - 1]:
          dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j])
          else:
          dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        return dp[-1][-1]