线性dp：最长公共子序列
最长公共子序列[*]本文讲解的题与leetcode1143.最长公共子序列这题一样，阅读完可以挑战一下。
力扣题目链接
题目叙述：
给定两个字符串，输出其最长公共子序列，并输出它的长度
输入：
ADABEC和DBDCA输出：
DBC
3解释
最长公共子序列是DBC，其长度为3
动态规划思路：
[*]我们这题先构建一个模型，我们使用两个指针i,j ，分别用于遍历a字符串，b字符串。如图所示：
[*]然后我们可以设想一个状态变量，也就是一个函数。一个关于两个变量相关的函数，这在代码中体现为二维数组f。
[*]然后f表示什么呢？表示序列a和b的最长公共子序列的长度
状态变量的含义
[*]在这里的状态变量为f，它的含义是a的前i个字符与b的前j个字符的最长公共子序列的长度
[*]现在就要观察a,b是否在当前的最长公共子序列当中。
[*]具体情况如下图：
递推公式：
[*]f可以分为三种情况讨论，就是：
[*]a，b都在最长公共子序列当中，也就是a==b
[*]a!=b，并且a不在公共子序列当中。
[*]a!=b，并且b不在公共子序列当中。
[*]那我们的递推公式就可与分为两种情况：
[*]f=f+1 （a==b）
[*]f=max(f,f) （a!=b）
[*]显而易见，我们的边界条件为：
[*]f=0
[*]f=0
//m是a字符串的长度，n是b字符串的长度for(int i=1;i 感谢分享，下载保存了，貌似很强大 这个好，看起来很实用 感谢，下载保存了 感谢分享，下载保存了，貌似很强大 不错，里面软件多更新就更好了 这个好，看起来很实用 谢谢分享，试用一下 收藏一下 不知道什么时候能用到 热心回复！ 谢谢分享，辛苦了 这个有用。 感谢，下载保存了 yyds。多谢分享 前排留名，哈哈哈 鼓励转贴优秀软件安全工具和文档！ 东西不错很实用谢谢分享 感谢，下载保存了 谢谢分享，辛苦了 感谢，下载保存了
页:
[1]
2