动态规划问题 —— 最长公共子序列

淩亂°似流年 2022-02-19 05:43 243阅读 0赞

### 题目描述 ###

链接：[https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a][https_www.nowcoder.com_questionTerminal_c996bbb77dd447d681ec6907ccfb488a]

时间限制：3秒；空间限制：32768K

对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A\[Ui\] == B\[Vi\]。

给定两个字符串**A**和**B**，同时给定两个串的长度**n**和**m**，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例：

"1A2C3D4B56",10,"B1D23CA45B6A",12
    返回：6

## 解题思路 ##

定义一个矩阵**z\[m+1\]\[n+1\]**，其中**z\[i\]\[j\]**代表字符串**A**中的前**i**个字符串和字符串**B**的前**j**个字符串的最长公共子序列。其中**z\[0\]\[j\]**行与**z\[i\]\[0\]**代表矩阵的第一行和第一列，其值均为0；接下来考虑求**z\[i\]\[i\]**时，先判断**A\[i\]**和**B\[j\]**是否相同，如果相同就是**z\[i-1\]\[j-1\]+1**，相当于在两个字符串都去掉一个字符时的最长公共字串**再加1**；否则取**z\[i\]\[j-1\]**和**z\[i-1\]\[j\]**中最大值；于是，从**z\[1\]\[1\]**开始，依照从左到右、从上到下的次序计算整个矩阵z，矩阵**z右下角的值**即为串A和B的最长公共子序列。

测试样例对应的矩阵z为：

\[\[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\],  
 \[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1\],  
 \[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\],  
 \[0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2\],  
 \[0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2\],  
 \[0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3\],  
 \[0, 1, 1, 2, 3, 3, 3, 3, 3, 3, 3\],  
 \[0, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3\],  
 \[0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4\],  
 \[0, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5\],  
 \[0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5\],  
 \[0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6\],  
 \[0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6\]\]

示例程序：

# -*- coding:utf-8 -*-
    class LCS:
        def findLCS(self, A, n, B, m):
            # write code here
            z = [[0 for i in range(n+1)] for j in range(m+1)]
            for i in range(1,m+1):
                for j in range(1,n+1):
                    if A[j-1]==B[i-1]:
                        z[i][j] = z[i-1][j-1] + 1
                    else:
                        z[i][j] = max(z[i-1][j],z[i][j-1])
            return z[m][n]

[https_www.nowcoder.com_questionTerminal_c996bbb77dd447d681ec6907ccfb488a]: https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a