刷题的时候看见这道题,一道简单的DP,找最长子序列的长度的。当时还想了一下怎么找具体序列是什么,结果没有接着想下去。。面试时候状态也不好,当时状态转移方程都没写对。。太菜。。找工作不止,刷题不息

题目

  • dp[i][j]定义为str1的前i个字符和str2的前j的字符之间的最长公共子序列的最大长度。所以当其中一个为空时,第0行/列初始化为0
  • str1的第i个字符与str2的第j个字符相等时,dp[i][j]dp[i-1][j-1]的值+1
  • str1的第i个字符与str2的第j个字符不相等时,dp[i][j]dp[i-1][j]dp[i][j-1]中较大的一个

dp数组的样子

1
2
3
4
5
6
7
8
9
10
11
def Longest_Common_Subsequence(s1,s2):
l1 = len(s1)
l2 = len(s2)
dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)]
for i in range(1,l1+1):
for j in range(1,l2+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])
return dp[-1][-1]

上面已经能A了力扣的这道题,但是面试遇到的是要输出最大的子序列是什么,只要额外定义一个memo二维数组,保存当前位置的数是由上面三种方式中的哪一种转移来的就好了,这里用1,2,3来区分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def Longest_Common_Subsequence(s1,s2):
l1 = len(s1)
l2 = len(s2)
dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)]
memo = [[0 for _ in range(l2+1)] for _ in range(l1+1)]
for i in range(1,l1+1):
for j in range(1,l2+1):
if s1[i-1]==s2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
memo[i][j] = 1
else:
if dp[i-1][j]>=dp[i][j-1]:
dp[i][j] = dp[i-1][j]
memo[i][j] = 3
else:
dp[i][j] = dp[i][j-1]
memo[i][j] = 2
x = l1
y = l2
start = (x,y)
res = []
while x and y:
if memo[x][y]==2:
y = y-1
elif memo[x][y]==3:
x = x-1
else:
res = [s1[x-1]]+res
x-=1
y-=1
print(''.join(res))

对于以下例子,

s1 = ‘1A2C3D4B56’
s2 = ‘B1D23CA45B6A’

可能的输出为:12C4B6123456

不同输出就取决于,dp[i-1][j]dp[i][j-1]相等时,memo中记录的是2还是3。


真的简单,当时还是紧张了吧,对不起态度这么好的小米面试官啦