最长公共子序列问题用动态规划解,并有改进,python代码
时间: 2024-02-13 11:01:35 浏览: 26
最长公共子序列问题是指找到两个字符串中最长的公共子序列,可以用动态规划的思想解决。以下是Python代码实现:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
c = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i][j - 1], c[i - 1][j])
return c[m][n]
```
其中,c[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列长度。如果str1[i-1]等于str2[j-1],则最长公共子序列长度加1,否则取左边或上边的最大值。最终返回c[m][n]即为最长公共子序列长度。
改进的做法是使用滚动数组,节省空间复杂度。代码如下:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
c = [0] * (n + 1)
for i in range(1, m + 1):
pre = 0
for j in range(1, n + 1):
temp = c[j]
if str1[i - 1] == str2[j - 1]:
c[j] = pre + 1
else:
c[j] = max(c[j - 1], c[j])
pre = temp
return c[n]
```
这里只使用了一维数组c来存储最长公共子序列长度,每次更新c[j]时需要用到前一轮的c[j],因此需要一个变量pre来保存前一轮的值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)