算法题:最长公共子序列

最长公共子序列(LCS)是典型的动态规划问题,如果不理解动态规划请移步先看这篇动态规划的总结,否则本篇文章中的代码实现会不理解的哟!

LCS问题的一个变种就是求最长单调递增子序列,它的一种简易求解方法就是先将原序列A进行排序得到序列B,然后求解序列A和序列B的最长公共子序列。

1.问题描述

 

2.最优子结构和子问题重叠

 

3.5种实现方式

根据LCS的递推公式

(1)从中可以看出计算c[i][j]时只需要2行即可,前一行(i-1)和当前行(i),每行的长度是min{m,n},首先初始化前一行都为0,然后计算当前行的值,当要计算下一行之前将当前行的值复制到前一行中即可。

(2)从递推公式中还可以看出计算当前行i的话,其实只需要一行再加上O(1)的额外空间就行了。因为计算c[i][j]只需要前一行中c[i-1][k] (k>=j-1)的数据,对于k<j-1的数据都是没有用的,而当前行c[i]l的数据都是有用的,要用来计算下一行的值,所以,可以在计算当前行的时候,将当前行的前面计算好的部分复制到前一行中对应位置上,但是c[i][j-1]除外,因为c[i-1][j-1]也是需要的,所以需要额外的O(1)的空间保存c[i][j-1]。

LCS的五种实现:分别为0:直接递归;1:带备忘录的递归;2:使用二维数组保存结果的迭代;3:使用2个一维数组保存结果的迭代;4:使用1个一维数组和额外的O(1)空间保存结果的迭代。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

1 6 收藏 评论

关于作者:五道口宅男潇涧

平凡之路,平凡如我! 个人主页 · 我的文章 · 5 ·    

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部