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

定义： d p [ i ] [ j ] dp[i][j] dp[i][j]表示字符串 a ⁡ \operatorname a a 从索引 0 0 0 到索引 i i i ，和字符串 b ⁡ \operatorname b b 从索引 0 0 0 到索引 j j j 的最长公共子序列

边界：第一行和第一列可以通过状态转移方程进行初始化

状态转移方程： d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1 , a ⁡ [ i ] = b ⁡ [ j ] max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) , a ⁡ [ i ] ≠ b ⁡ [ j ] d p[i][j]= \begin{cases}d p[i-1][j-1]+1, & \operatorname a[i]=\operatorname b[j] \\ \max (d p[i-1][j], d p[i][j-1]), & \operatorname a[i] \neq \operatorname b[j]\end{cases} dp[i][j]={dp[i−1][j−1]+1,max(dp[i−1][j],dp[i][j−1]),​a[i]=b[j]a[i]​=b[j]​

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        # 定义
        N = len(a)
        M = len(b)
        dp=[[0]*M for _ in range(N)]
        # 初始化边界 
        for i in range(N):
            if b[0] == a[i]:
                dp[i][0] = 1
            elif i > 0:
                dp[i][0] = dp[i-1][0] 
        
        for i in range(M):
            if b[i] == a[0]:
                dp[0][i] = 1
            elif i > 0:
                dp[0][i] = dp[0][i-1]
        # 状态转移，先行后列，先列后行遍历皆可	
        for i in range(1,N):
            for j in range(1,M):
                if a[i]==b[j]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[N-1][M-1]

如果是考虑输出最长公共子序列的字符串具体值，则可将dp存储具体的值，判断的时候则判断字符串的长度

链接：https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11

class Solution:
    def LCS(self , a , b):
        if len(a)==0 or len(b) == 0:
            return "-1"
                # 定义
        N = len(a)
        M = len(b)
        dp=[[""]*M for _ in range(N)]
        # 初始化边界 
        flag = 1
        for i in range(N):
            if b[0] == a[i] and flag:
                dp[i][0] = a[i]
                flag = 0
            elif i > 0:
                dp[i][0] = dp[i-1][0] 
        flag = 1
        for i in range(M):
            if b[i] == a[0] and flag:
                dp[0][i] = b[i]
                flag = 0
            elif i > 0:
                dp[0][i] = dp[0][i-1]
        # 状态转移，先行后列，先列后行遍历皆可	
        for i in range(1,N):
            for j in range(1,M):
                if a[i]==b[j]:
                    dp[i][j] = dp[i-1][j-1]+a[i]
                elif len(dp[i][j-1])>len(dp[i-1][j]):
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[N-1][M-1] if len(dp[N-1][M-1]) != 0 else "-1"