建站平台是给谁用的,怀化冰山涯IT网站建设公司,虚拟空间做网站,seo技术培训教程动态规划
BM65 最长公共子序列#xff08;二#xff09;
这道题是动态规划的典型例题。
思路
题目要求获取最长公共子序列#xff0c;我们要先求最长公共子序列的长度#xff0c;然后根据这个长度倒推从而获取这个子序列。注意#xff1a;子序列不是子串#xff0c;子…动态规划
BM65 最长公共子序列二
这道题是动态规划的典型例题。
思路
题目要求获取最长公共子序列我们要先求最长公共子序列的长度然后根据这个长度倒推从而获取这个子序列。注意子序列不是子串子串要求所有字符在原字符串中的位置必须连续子序列不要求连续只要求相对位置不变。这一点会影响dp数组的定义。 设存在字符串 s 1 和 s 2 设存在字符串s1和s2 设存在字符串s1和s2
定义dp数组并初始化。 d p [ i ] [ j ] 表示在截止到 s 1 [ i − 1 ] 和 s 2 [ j − 1 ] 的字符串中最长公共子序列的 长度。注 : 在这个定义中 , 此时的最长公共子序列的末尾元素不一定 是 s 1 [ i − 1 ] 或 s 2 [ j − 1 ] dp[i][j]表示在截止到s1[i-1]和s2[j-1]的字符串中最长公共子序列的\\长度。注:在这个定义中,此时的最长公共子序列的末尾元素不一定\\是s1[i-1]或s2[j-1] dp[i][j]表示在截止到s1[i−1]和s2[j−1]的字符串中最长公共子序列的长度。注:在这个定义中,此时的最长公共子序列的末尾元素不一定是s1[i−1]或s2[j−1]
这里为了省去初始化时的分类讨论我们可以将dp数组初始化成一个 l e n g t h ( s 1 ) 1 length(s1)1 length(s1)1行 l e n g t h ( s 2 ) 1 length(s2)1 length(s2)1列的全0数组。此时有 d p [ 0 ] [ j ] d p [ i ] [ 0 ] 0 dp[0][j]dp[i][0]0 dp[0][j]dp[i][0]0
从前到后遍历两个字符串开始状态转移。状态转移方程如下 { d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 s 1 [ i − 1 ] s 2 [ j − 1 ] d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) s 1 [ i − 1 ] ≠ s 2 [ j − 1 ] 1 ≤ i ≤ l e n g t h ( s 1 ) , 1 ≤ j ≤ l e n g t h ( s 2 ) \begin{align} \begin{cases} 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]\neq s2[j-1]\\ \\ 1\leq i\leq length(s1),1\leq j\leq length(s2) \end{cases} \end{align} ⎩ ⎨ ⎧dp[i][j]dp[i−1][j−1]1dp[i][j]max(dp[i−1][j],dp[i][j−1])1≤i≤length(s1),1≤j≤length(s2)s1[i−1]s2[j−1]s1[i−1]s2[j−1] 解释一下这个状态转移方程。
当 s 1 [ i − 1 ] s 2 [ j − 1 ] s1[i-1]s2[j-1] 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即 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 dp[i][j]dp[i-1][j-1]1 dp[i][j]dp[i−1][j−1]1当 s 1 [ i − 1 ] ≠ s 2 [ j − 1 ] s1[i-1]\neq s2[j-1] s1[i−1]s2[j−1]说明s1[i-1]和s2[j-1]不可能同时属于最长公共子序列但有可能它俩其中之一属于最长公共子序列。因此 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j]max(dp[i-1][j],dp[i][j-1]) dp[i][j]max(dp[i−1][j],dp[i][j−1]) 状态转移完成后 d p [ l e n g t h ( s 1 ) ] [ l e n g t h ( s 2 ) ] dp[length(s1)][length(s2)] dp[length(s1)][length(s2)]一定是最长公共子序列的长度。 从 d p [ l e n g t h ( s 1 ) ] [ l e n g t h ( s 2 ) ] dp[length(s1)][length(s2)] dp[length(s1)][length(s2)]开始倒推寻找最长公共子序列。根据dp数组转移的方向不断往前组装字符。 只有当 d p [ i ] [ j ] dp[i][j] dp[i][j]同时满足如下3个条件才能说明字符s1[i-1]和s2[j-1]都属于最长公共子序列将s1[i-1]或s2[j-1]添加进序列。 { d p [ i ] [ j ] ≠ d p [ i − 1 ] [ j ] d p [ i ] [ j ] ≠ d p [ i ] [ j − 1 ] d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] \begin{align} \begin{cases} dp[i][j]\neq dp[i-1][j]\\ \\ dp[i][j]\neq dp[i][j-1]\\ \\ dp[i][j]dp[i-1][j-1] \end{cases} \end{align} ⎩ ⎨ ⎧dp[i][j]dp[i−1][j]dp[i][j]dp[i][j−1]dp[i][j]dp[i−1][j−1] 第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 -1dp [[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] 1else: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-1elif dp[i][j] dp[i][j-1]:#如果从上方向来j j-1elif dp[i][j] dp[i-1][j-1]:#只有从左上方向来才是字符相等i i-1j j-1lcs.append(s1[i])#这样得到的最长公共子序列是逆序的res while len(lcs) ! 0:res lcs[-1] #依次将lcs中末尾元素插入lcs.pop() #弹出末尾元素#如果两个序列完全不同if res :return -1else:return resif __name__ __main__:s1 input()s2 input()a Solution()print(a.LCS(s1,s2))
