48. 最长公共子序列.md

求两字符串的最长公共子序列

def longestCommonSubsequence(s, t):
    #假设字符串 s 和 t 的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，其中 dp[i][j] 表示 s[0:i] 和 t[0:j]的最长公共子序列的长度。
    m = len(s)
    n = len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[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[-1][-1]