LCS学习笔记

81 阅读 0 评论 54 点赞

我是靠谱客的博主简单帅哥，最近开发中收集的这篇文章主要介绍LCS学习笔记，觉得挺不错的，现在分享给大家，希望可以做个参考。

状态的表示：f[i][j]表示第一个字符串的前i个字符，与第二个字符串的前j个字符，能形成的最长公共子序列的长度

边界条件：f[0][i]=f[i][0]=0

因为一个空字符串和另一个长度为i的字符串能形成的最长公共子序列长度为0

这样的话，答案的表示就是f[s1.size()][s2.size()]

A[i]==B[j]时，说明A[i]与B[j]正好是相等的，这可以让最长公共子序列的长度增加1，接下来可以转化到A的前i-1个字符与B的前j-1个字符能形成的最长公共子序列的长度这个子问题，所以f[i][j]=f[i-1][j-1]+1

所有动态规划的题目都需要把四个要素考虑清楚： 1状态的表示 2状态转移方程 3边界条件 4答案的表示

### 未完善

以上就是简单帅哥为你收集整理的LCS学习笔记的全部内容，希望文章能够帮你解决LCS学习笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。