最长公共子序列可通过经典的动态规划问题的求解方式

  1. 建立dp表,明确dp的含义
  2. 定义base case
  3. 确定转移方程
    第一步：因为是对两个字符串的求解问题,dp为二维,dp[i][j]表示字符串s1[:i]与字符串s2[:j]之前最大子序列的长度,考虑空字符串,i,j 从1 开始遍历
    第二步: 在定义 base case 时, 由于空字符串, dp[0][0] = 0
    第三步: 确定状态转移过程, 求解 dp[i][j] 时,看 看 i, j 之前的状态数据, 即 s1[i - 1] 和 s2[j - 1] 是否相等;
    (1) s1[i - 1] == s2[j - 1] 则 dp[i][j] 是从 dp[i - 1][j - 1] 转移过来的
    (2) s1[i - 1] != s2[j - 1], 因为要求的是最长的公共(相等)子序列, 则取 dp[i - 1][j] 和 dp[i][j - 1] 中较大的一个
    求公共子序列长度的代码如下:
    def LCS(self , s1 , s2 ):
     # write code here
     dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
     res = ''
     for i in range(1, len(s1) + 1):
         for j in range(1, len(s2) + 1):
             if s1[i - 1] == s2[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]
    本题中需要给出最长公共子序列的字符串，因此还需要构造出具体的字符串生成方式;
    由于dp表构建出了两个字符串在对比的过程中,状态是如何转移的,因此构建公共子序列字符串时，可在dp表构建之后，再根据dp表中i,j的转移方式，当 s1[i - 1] == s2[j - 1]时，将字符添加至公共子序列中;
    代码如下(参考题解中大佬的代码):
    def LCS(self , s1 , s2 ):
     # write code here
     dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
     res = ''
     for i in range(1, len(s1) + 1):
         for j in range(1, len(s2) + 1):
             if s1[i - 1] == s2[j - 1]:
                 dp[i][j] = dp[i - 1][j - 1] + 1
             else:
                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
     if dp[-1][-1] == 0:
         return -1
     i, j = len(s1), len(s2)
     while i > 0 and j > 0:
         if s1[i - 1] == s2[j - 1]:
             res += s1[i - 1]
             i -= 1
             j -= 1
         elif dp[i - 1][j] > dp[i][j - 1]:
             i -= 1
         else:
             j -= 1
     return res[::-1]