题解 | #最长公共子序列(一)#

最长公共子序列长度，动态规划——时间O(mn)，空间O(min(m,n))

两个字符串的公共子序列，是由两个字符串同时含有，且出现顺序一致的字符所构成的序列，核心在于同时含有和顺序一致。
同时含有表示存在下标i和j使得s1[i]=s2[j]，顺序一致表示如果还存在下标p, q使得s1[p]=s2[q]，且s1[i]与s1[p]组成公共子序列，那么必有p > i, q>j 或者p < i, q < j。则最长公共子序列长度问题就变成了m*n的二维空间中搜索满足条件点的问题。
二维空间中，如果给i,j点一个状态dp[i][j]，由于原问题的解包含所有子问题的解，所以直接让dp[i][j]代表子问题s1[:i+1]与s2[:j+1]最长公共子序列长度，如果它可以由已知点状态转移而来，那么就可以用动态规划来解决原问题。
遍历m*n空间搜索满足条件的点：如果s1[i]=s2[j]，则同时含有的条件满足，现在只需要找到最近一个满足顺序一致的已知点，并把该点状态加一即可得到当前点状态，显然(i-1, j-1)满足条件，所以此时dp[i][j]=dp[i-1][j-1] + 1。如果s1[i]!=s2[j]，即同时含有不满足，也就没有了顺序一致的问题，直接从离当前点最近的两个已知点中继承最大状态即可，此时dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

由于每一行的状态只与上一行有关，可以优化dp为一维向量，但此时需要一个变量来记录(i-1, j-1)状态。

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        if not s1 or not s2: return 0
        if len(s1) > len(s2):
            s1, s2 = s2, s1          # 让s1表示短串
        m, n = len(s1), len(s2)
        dp = [0]*(m+1)              # 根据短串的长度构造dp
        for i in range(n):
            pre_dp = dp[0]           # 初始的[i-1][j-1]位置的dp，为dp[0]，一直为空，便于算边缘位置
            for j in range(m):
                if s1[j] == s2[i]:     # 相等        
                    tmp = dp[j+1]      # 记录下一个[i-1][j-1]位置的dp备用，为之前的dp[j+1]
                    dp[j+1] = pre_dp + 1 # 状态转移
                    pre_dp = tmp
                else:
                    pre_dp = dp[j+1]   # 记录下一个[i-1][j-1]位置的dp备用，为之前的dp[j+1]
                    dp[j+1] = max(dp[j+1], dp[j]) # 状态转移
        return dp[-1]