动态规划

BM65 最长公共子序列（二）

这道题是动态规划的典型例题。

思路

题目要求获取最长公共子序列，我们要先求最长公共子序列的长度，然后根据这个长度倒推从而获取这个子序列。注意：子序列不是子串，子串要求所有字符在原字符串中的位置必须连续，子序列不要求连续，只要求相对位置不变。这一点会影响dp数组的定义。
$$设存在字符串s1和s2；$$

1. 定义dp数组并初始化。
   $$\begin{gathered} dp[i][j]表示在截止到s1[i-1]和s2[j-1]的字符串中，最长公共子序列的 \\ 长度。注:在这个定义中,此时的最长公共子序列的末尾元素不一定 \\ 是s1[i-1]或s2[j-1] \end{gathered}$$

这里为了省去初始化时的分类讨论，我们可以将dp数组初始化成一个$length(s1)+1$行$length(s2)+1$列的全0数组。此时有$$dp[0][j]=dp[i][0]=0$$

2. 从前到后遍历两个字符串，开始状态转移。状态转移方程如下：

$$\begin{array}{r}\{\begin{array}{ll}dp[i][j]=dp[i-1][j-1]+1& s1[i-1]=s2[j-1]\\ & \\ dp[i][j]=max(dp[i-1][j],dp[i][j-1])& s1[i-1]\ne s2[j-1]\\ & \\ 1\le i\le length(s1),1\le j\le length(s2)& \end{array}\end{array}$$
解释一下这个状态转移方程。

• 当$s1[i-1]=s2[j-1]$，说明字符s1[i-1]和字符s2[j-1]相同，它们都属于最长公共子序列；在截止到s1[i-1]和s2[j-1]的字符串中最长公共子序列的长度 = 在截止到s1[i-2]和s2[j-2]的字符串中最长公共子序列的长度+1，即$dp[i][j]=dp[i-1][j-1]+1$
• 当$s1[i-1]\ne s2[j-1]$，说明s1[i-1]和s2[j-1]不可能同时属于最长公共子序列，但有可能它俩其中之一属于最长公共子序列。因此$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$

3. 状态转移完成后，$dp[length(s1)][length(s2)]$一定是最长公共子序列的长度。

4. 从$dp[length(s1)][length(s2)]$开始倒推寻找最长公共子序列。根据dp数组转移的方向，不断往前组装字符。

   只有当$dp[i][j]$同时满足如下3个条件，才能说明字符s1[i-1]和s2[j-1]都属于最长公共子序列，将s1[i-1]或s2[j-1]添加进序列。
   $$\begin{array}{r}\{\begin{array}{l}dp[i][j]\ne dp[i-1][j]\\ \\ dp[i][j]\ne dp[i][j-1]\\ \\ dp[i][j]=dp[i-1][j-1]\end{array}\end{array}$$

5. 第4步得到的序列其实是最长公共子序列的逆序，将其逆转就得到了题目所求的最长公共子序列。

代码

import numpy as np
import  pandas as pd

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        """dp[i][j]：截至到s1[i-1]和s2[j-1]，搜索到的最长公共子序列长度"""
        if s1 is None or s2 is None:
            return "-1"
        dp = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]
        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])
        # print(dp)
        #寻找最长公共子序列
        i = len(s1)
        j = len(s2)
        lcs = []
        while dp[i][j] != 0:
            if dp[i][j] == dp[i-1][j]:#如果从左方向来
                i = i-1
            elif dp[i][j] == dp[i][j-1]:#如果从上方向来
                j = j-1
            elif dp[i][j] > dp[i-1][j-1]:#只有从左上方向来才是字符相等
                i = i-1
                j = j-1
                lcs.append(s1[i])#这样得到的最长公共子序列是逆序的
        res = ''
        while len(lcs) != 0:
            res += lcs[-1] #依次将lcs中末尾元素插入
            lcs.pop() #弹出末尾元素

        #如果两个序列完全不同
        if res == '':
            return "-1"
        else:
            return res

if __name__ == '__main__':
    s1 = input()
    s2 = input()
    a = Solution()
    print(a.LCS(s1,s2))