题目：最长公共子序列
剑指 Offer II 095. 最长公共子序列
解题思路
经典动态规划题目
设一个动态规划二维数组dp[m][n]
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
对比text1[i]、text2[j]，如果text1[i]=text2[j]，则dp[i][j]=dp[i-1][j-1]+1
如果text1[i]!=text2[j]，则dp[i][j]=max(dp[i-1][j], dp[i][j-1])
视频讲解：最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming
代码实现
'''
-*- coding: utf-8 -*-
@author: Qiufen.Chen
@time: 2021/8/14:20:56
'''
def longestCommonSubsequence(text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1,n+1):
c1 = text1[i-1]
c2 = text2[j-1]
if c1 == c2:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
text1 = "ABCBDAB"
text2 = "BDCABA"
print(longestCommonSubsequence(text1, text2))
leetcode? 392. 判断子序列
注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
解题思路?
（1）确定dp数组：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
（2）确定递推公式：if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1；因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1；if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1]。
（3）dp数组如何初始化：从递推公式可以看出dp[i][j]依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
（4）确定遍历顺序：同理从从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右。
参考：「代码随想录」带你学透DP子序列问题！392. 判断子序列【动态规划经典题目】详解 - 判断子序列 - 力扣（LeetCode） (leetcode-cn.com)
代码实现
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m = len(s) # m行
n = len(t) # n列
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
c1 = s[i-1]
c2 = t[j-1]
if c1 == c2:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = dp[i][j-1]
return True if dp[m][n] == len(s) else False
|