最长公共子序列的动态规划算法分析

我的理解和分析

我觉得照最长公共子序列是个比较经典,基础的动态规划算法,所以我专门把我的理解和方法记录下来,以后在来看看自己的思维有什么变化.

1. 问题的抽象

类似于问题重述,首先先把问题抽象一下.

算法目标相当于是要寻找两个字符串中最长的相同字串,并且字串是可以跳选的,什么意思呢,就是假设有两个字串:

“今天会下雨” 和 “天要下大雨” 那么取出第一个字串的1,3,4和第二个字串的0,2,4都是”天下雨”,即满足条件.

那么用两个字串张成一个二维区域,很容易就能找到在二维区域中问题的抽象

# 这堆代码是用来画图的,可以不用看
import pandas as pd
s1,s2 = "今天会下大雨" , "天大有可能要下大雨"
index,columns = [0],[0]
for i in range (len(s1)):
    columns.append(s1[i]+"-"+str(i))
for i in range (len(s2)):
    index.append(s2[i]+"-"+str(i))

matrix = [[0 for i in range(len(s1)+1)]  for j in range(len(s2)+1)]
matrix[0][0]="?"
matrix = pd.DataFrame(matrix,index=index,columns=columns)

def setcolor(val):
    color = [['background-color: white' for i in range(len(s1)+1)]  for j in range(len(s2)+1)]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i]==s2[j]:
                color[j+1][i+1]='background-color: yellow'
    return pd.DataFrame(color,index=index,columns=columns)
matrix.style.apply(setcolor, axis=None)
0 今-0 天-1 会-2 下-3 大-4 雨-5
0 ? 0 0 0 0 0 0
天-0 0 0 0 0 0 0 0
大-1 0 0 0 0 0 0 0
有-2 0 0 0 0 0 0 0
可-3 0 0 0 0 0 0 0
能-4 0 0 0 0 0 0 0
要-5 0 0 0 0 0 0 0
下-6 0 0 0 0 0 0 0
大-7 0 0 0 0 0 0 0
雨-8 0 0 0 0 0 0 0

问题就被抽象为了:

  • 约束规则: 一个二维指针*,从(0,0)出发,需要到达(雨-4,雨-4),但它在白色区域中只能向右或者向下移动而不能向上或向左.另外,在右下侧为黄色方格时,它也能往右下移动 (*:可以把它把简单理解为一个点,稍后我会解释为什么我叫它二维指针)

  • 目标:在二维指针行进过程中,经过尽量多的黄色方格

为什么我要这么抽象?

  • 二维指针其实就是在两个字符串上的指针对,由于公共子序列读出的顺序是不能够打乱的,指针在字符串上移动时就只能朝一个方向
  • 二维指针在白色方格上行进时,就是在跳过原字符串上对子序列没有贡献的字符;而在经过黄色方格时,两个维度上读到的字符是一样的,就能放进子序列中

2.问题的解决

抽象为二维行进以后,问题就比较容易解答了.我们在每一个方格(二维位置)中存放一个数字,这个数字代表着二维指针行进到这个位置能经过的最多黄格数量

也就是说:

  • 对白格位置,数字等于它的左侧或它的上侧方块中较大的一个.这是因为因为经过白格无法增加数字.
  • 对黄格位置,数字等于它的左上侧方格数字加1,这是由于如要经过黄格,二维指针只能从黄格的左上方格向右下跳,并且能够增加数字

也就变成了:

# 这堆代码是用来画图的,可以不用看
matrix=[[0 for i in range(len(s1)+1)]  for j in range(len(s2)+1)]

#遍历所有方格
for p1 in range(len(s1)):
    for p2 in range(len(s2)):
        if s1[p1] == s2[p2]: #是黄格
            matrix[p2+1][p1+1] = matrix[p2][p1]+1
        else: #是白格
            matrix[p2+1][p1+1] =max(matrix[p2][p1+1],matrix[p2+1][p1])

matrix = pd.DataFrame(matrix,index=index,columns=columns)
matrix.style.apply(setcolor, axis=None)
0 今-0 天-1 会-2 下-3 大-4 雨-5
0 0 0 0 0 0 0 0
天-0 0 0 1 1 1 1 1
大-1 0 0 1 1 1 2 2
有-2 0 0 1 1 1 2 2
可-3 0 0 1 1 1 2 2
能-4 0 0 1 1 1 2 2
要-5 0 0 1 1 1 2 2
下-6 0 0 1 1 2 2 2
大-7 0 0 1 1 2 3 3
雨-8 0 0 1 1 2 3 4

于是就找到了最大公共子序列长度(最右下角那个方格):4

然后画出二维指针行进的路线,经过的黄格就是最大公共子序列里的字符

这时候已经大致理解了这个问题,就可以去看严谨描述了,比如这个

示例:这是一个用来寻找最长公共子序列的函数,输入两个字符串,返回最长公共子序列长度

def find_lcseque(s1, s2):
  matrix=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]
  for p1 in range(len(s1)):
    for p2 in range(len(s2)):
      if s1[p1] == s2[p2]:
        matrix[p1+1][p2+1] = matrix[p1][p2]+1
      else:
        matrix[p1+1][p2+1] =max(matrix[p1][p2+1],matrix[p1+1][p2])
  return matrix[-1][-1]
s1,s2="sertyulilvtyesryiunivtcrxuey5rcbuidewioufhweilufcjlewcfjweuidfio328r8347wedjesilkdfj32o8reuwelijdel","ewuirwleucfhlwiedfhwlieufchswfuchswefuihwlifuhwdficjewfuijfhu;iwejf;erfjweiufuhrewyp87rfhy;sdiufewu89p"
find_lcseque(s1, s2)
40
本文总字数: 2502