1143.最长公共子序列.md

1143. 最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

解法一：dp

dp[i][j]表示s[0...i-1]与s2[0...j-1]的最长公共子序列（LCS)长度，为什么偏移一位？为了预留i=0和j=0分别表示s1和s2为空串 1、当s[i] == s2[j]时，s[0...i]与s2[0...j]的LCS长度等于s[0...i-1]与s2[0...j-1]的LCS长度加一，即： dp[i][j] = dp[i-1][j-1] +1 2、当s[i] != s2[j]时，s[0...i]与s2[0...j]LCS长度，取s[0...i-1]与s2[0...j-1]，或s[0...i-1]与s2[0...j-1]的LCS最大值，即： dp[i][j] = max(dp[i][j-1], dp[i-1][j])

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        m=len(s1)
        n=len(s2)
        dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] +1
                else:
                    #至少有一个字符不在LCS中
                    #都试一下，找LCS最长的
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]