最长公共子序列 设:a[0:n-1]和b[0:m-1]是两个字符串数组,由’abcdef’中的字符组成, a[]=”acdfecdfbb”; b[]=”bcdfaedfbc” 1)请实现找a,b的最长公共子序列算法。 2)实现空间优化的最长子序列算法。
时间: 2024-05-21 14:13:12 浏览: 22
1)找a,b的最长公共子序列算法:
我们可以使用动态规划的思想来解决这个问题。
首先,我们定义一个二维数组dp,其中dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列的长度。
然后,我们可以根据以下两种情况来求解dp[i][j]:
1. 如果a[i] == b[j],那么dp[i][j] = dp[i-1][j-1] + 1;
2. 如果a[i] != b[j],那么dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
最终,dp[n-1][m-1]就是a和b的最长公共子序列的长度。
不过,这种算法只能求出最长公共子序列的长度,而不能求出具体的最长公共子序列。
2)空间优化的最长子序列算法:
在上面的算法中,我们使用了一个二维数组来保存状态,因此空间复杂度为O(nm)。但实际上,我们只需要用到dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]这三个状态,因此可以将二维数组优化为一维数组。
具体地,我们可以定义一个一维数组dp,其中dp[j]表示a[0:i]和b[0:j]的最长公共子序列的长度。在每次更新dp[j]时,我们需要用到之前的dp[j-1]、dp[j]和dp[j-1]这三个状态。因此,我们可以用一个变量pre来保存dp[j-1]的值,用一个变量cur来保存dp[j]的值,用一个变量tmp来保存dp[j-1]的值。在更新dp[j]时,我们先将pre赋值给tmp,然后将cur更新为max(tmp, dp[j]),最后再将cur赋值给pre。这样,我们就可以用O(min(n,m))的空间复杂度来求解最长公共子序列的长度了。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)