刷题的时候看见这道题，一道简单的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’

可能的输出为：12C4B6和123456

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

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