C++动态规划解决最长公共子序列

动规非常经典的一道题目，由于需要用到二维数组——姑且算为中等难度的题目，其实和01背包有着极高的相似度，无论是实现还是理论。

今天这篇博客不讲过多的DP理论，重在讲解题目本身。其实有一定经验的同志都清楚，DP的难点在于想明白子问题分割的细节——也即列出正确的状态转移方程，只要方程正确，那么无论是用C++、Java甚至MATLAB，实现起来都很简单。

再来介绍题目本身，和最长公共子串不同的是——公共子序列中的元素可以是不连续的，但对于子串则必须连续。举个简单的例子：

对于ABBCC和ABCDE来说：

最长公共子序列可以不连续，因此是ABC
最长子串必须连续，因此是AB

一.子问题的划分

还是举上面的例子，对于这两个长度为5的子串，如果我们要得到他们之间的最长公共子序列，肯定要先知道其中一个减去一位后最长的子序列作为先导，又要以两者均减去一位后得到的最长子序列。

以此类推，实际上我们最终可以将子问题分解为只有0个字母时——两者的公共子序列。我们将这个状态也即子问题记为answer(X，Y)，即最小子问题为(0,0)，在编码中我们用二维数组DP表示，如下图：横纵两轴分别表示在目标子串之一包含该字母的情况下，二者的最长公共子序列~

二.初始化DP数组

这也是动态规划里面的一大基本操作，我们要人为地给出问题的初试解。在本题目中，当一个子串为长度为0时，另一个无论多长，二者的公共长度均为0，因此作出如下初始化：

实际上，任何需要用到二维数组的题目——比如01背包，横纵轴分别表示物品序号和当前背包重量，都是这样初始化DP数组的。

三.列出状态转移方程

我们先来看一个简单的情况：也即子问题（1,1）——两个序列均有一个字母的时候，由于用例二者头字母均为A，因此在当前情况下最长公共子序列长度为1。

继续观察一下：假如现在第一个串多了一位，而第二个不变，也即子问题（2,1）——由于我们要求的是公共的最大子序列，现在一个人多了一位，另一个不变——换句话说其实和这个人多了一位后对答案毫无影响！因此我们的（2,1）应该怎么填呢？是不是还是1！以此类推，（1,2）的答案也是1：

前面说到，单独一个加一位不影响什么结果，那如果两个人同时加呢？设想一下，比如我们先从（1,1）的基础上加一位变成（2,1），此时我们要计算（2,2），相当于第二个序列的扩充可能会带来一位的增加，因此我们的(2,2）必然是大于等于（2,1）的——即扩充长度是一个单调不减的过程。但实际上我们还得考虑(1,2)的情况，也即这两种都有可能因为扩充其中的一位，导致answer加一！所以我们的（2,2）应该是两者之中更大的一位！

最终结果如下图所示：红色的色块表示当前两个字符串中有新的一样的子列添加进来，因此需要加一。如果不相同就从上方和左边选一个最大的即可~

我们来编码实现一下：

#include <iostream>
#include <string> 
using namespace std;
int main()
{string s1,s2;cin>>s1;cin>>s2;int n1=s1.length(),n2=s2.length();int DP[n1+1][n2+1];//n1行，n2列，也即纵向为第一个字符串 for(int i=0;i<=n2;i++){for(int j=0;j<=n1;j++)DP[i][j]=0;//数据预处理，脏数据经常出现~ }for(int i=1;i<=n2;i++){for(int j=1;j<=n1;j++) {if(s1[j-1]==s2[i-1])//相等则从上个对角元素+1 DP[i][j]=DP[i-1][j-1]+1;elseDP[i][j]=max(DP[i-1][j],DP[i][j-1]);//不相等则从只增加其中一位后的情况中选一个大的 }}for(int i=0;i<=n2;i++){for(int j=0;j<=n1;j++)cout<<DP[i][j]<<" ";cout<<endl;}return 0;
}

没什么问题：