給定兩個(gè)字符串s1 和 s2，返回這兩個(gè)字符串的最長(zhǎng)公共子序列

這是關(guān)于2個(gè)字符串的dp模板問(wèn)題

以
s1 = 'ace'
s2 = 'babcde'為例
dptable如下

最長(zhǎng)公共子序列的dptable

那么我們根據(jù)狀態(tài)轉(zhuǎn)移方程

if str1[i] == str2[j]:
    # 當(dāng)前相同元素納入最長(zhǎng)公共子序列
    dp[i][j] = dp[i-1][j-1] + str1[i]
else:
    # 取左元素或者上元素中長(zhǎng)度最長(zhǎng)的一個(gè)
    if len(dp[i-1][j]) > len(dp[i][j-1]):
        dp[i][j] = dp[i-1][j]
    else:
        dp[i][j] = dp[i][j-1] 

如圖所示：

dp二維數(shù)組的狀態(tài)轉(zhuǎn)移圖

class Solution:
    def longestCommonSubsequence(self, str1, str2) -> int:
        m, n = len(str1), len(str2)

        # 構(gòu)建 DP table 和 base case。注意，dp table的規(guī)模是(m+1)*(n+1)，都外擴(kuò)了一層作為base case
        dp = [['' for i in range(n+1)] for j in range(m + 1)]
        
        # 開始填dp表
        for i in range(1, m + 1):
            for j in range(1, n + 1):

                # 進(jìn)行狀態(tài)轉(zhuǎn)移
                # 如果兩個(gè)指針指向的元素相等
                if str1[i - 1] == str2[j - 1]:
                    # 找到一個(gè) lcs 中的字符
                    dp[i][j] = dp[i-1][j-1] + str1[i - 1]
                # 如果兩個(gè)指針指向的元素不等
                else:
                    if len(dp[i-1][j]) > len(dp[i][j-1]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = dp[i][j-1]

        # 返回最長(zhǎng)公共子串長(zhǎng)度    
        return len(dp[-1][-1])
        # # 返回最長(zhǎng)公共子串
        # return dp[-1][-1]