线性dp：最长公共子序列
最长公共子序列[*]本文讲解的题与leetcode1143.最长公共子序列这题一样，阅读完可以挑战一下。
力扣标题链接
标题叙述：
给定两个字符串，输出其最长公共子序列，并输出它的长度
输入：
ADABEC和DBDCA输出：
DBC
3解释
最长公共子序列是DBC，其长度为3
动态规划思绪：
[*]我们这题先构建一个模型，我们利用两个指针i,j ，分别用于遍历a字符串，b字符串。如图所示：
https://img2024.cnblogs.com/blog/3476421/202408/3476421-20240819160040167-324712248.png
[*]然后我们可以设想一个状态变量，也就是一个函数。一个关于两个变量相干的函数，这在代码中体现为二维数组f。
[*]然后f体现什么呢？体现序列a和b的最长公共子序列的长度
状态变量的含义
[*]在这里的状态变量为f，它的含义是a的前i个字符与b的前j个字符的最长公共子序列的长度
[*]现在就要观察a,b是否在当前的最长公共子序列当中。
[*]具体环境如下图：
https://img2024.cnblogs.com/blog/3476421/202408/3476421-20240819162032119-336961171.png
递推公式：
[*]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
页:
[1]