带娃刷题第335天 动态规划算法 最长公共子串 LCS 递归 记忆化搜索

Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        n = len(a)
        m = len(b)
        @cache
        def lcs(i, j):
          if i < 0 or j < 0:
          return 0
          if a[i] == b[j]:
          return 1 + lcs(i - 1, j - 1)
          return max(lcs(i, j - 1), lcs(i - 1, j))
        ans = lcs(n - 1, m - 1)
        return ans