线性dp：最长公共子序列

最长公共子序列

• 本文讲解的题与leetcode1143.最长公共子序列这题一样，阅读完可以挑战一下。
  

力扣标题链接
标题叙述：

给定两个字符串，输出其最长公共子序列，并输出它的长度
输入：

1. ADABEC和DBDCA

复制代码

输出：

1. DBC
2. 3

复制代码

解释

最长公共子序列是DBC，其长度为3
动态规划思绪：

• 我们这题先构建一个模型，我们利用两个指针i,j ，分别用于遍历a字符串，b字符串。如图所示：
  

• 然后我们可以设想一个状态变量，也就是一个函数。一个关于两个变量相干的函数，这在代码中体现为二维数组f。
  
• 然后f[j]体现什么呢？体现序列a[1,2,3....i]和b[1,2,3....j]的最长公共子序列的长度
  

状态变量的含义

• 在这里的状态变量为f[j]，它的含义是a的前i个字符与b的前j个字符的最长公共子序列的长度
  
• 现在就要观察a,b[j]是否在当前的最长公共子序列当中。
  
• 具体环境如下图：
  

递推公式：

• f[j]可以分为三种环境讨论，就是：
  

• a，b[j]都在最长公共子序列当中，也就是a==b[j]
  
• a!=b[j]，并且a不在公共子序列当中。
  
• a!=b[j]，并且b[j]不在公共子序列当中。
  

• 那我们的递推公式就可与分为两种环境：
  
  
  
  • f[j]=f[i-1][j-1]+1 （a==b[j]）
    
  • f[j]=max(f[i-1][j],f[j-1]) （a!=b[j]）
    
  
  
• 显而易见，我们的边界条件为：
  
  
  
  • f[0][j]=0
    
  • f[0]=0
    
  
  

[code]//m是a字符串的长度，n是b字符串的长度for(int i=1;i