（为什么都更了这么多篇笔记了，这时候才讲这么基础的内容呢？因为我本来以为LCS这种简单的DP不用讲的，结果CF不久前考了LCS的变式，然后我发现由于自己对LCS一点都不熟，居然写不出来 ，于是决定还是写一下笔记。今后不排除你们还会看到最小生成树、背包等基础算法的笔记……）
最长公共子序列（Longest Common Subsequence，LCS）是动态规划中的经典问题，顾名思义，即求两个序列最长的公共子序列（可以不连续）。在本文中，我们规定用
表示序列 的最后一个元素，用 表示 去掉最后一个元素后的子序列， 表示s1和s2的LCS的长度。现在，假如我们有abdcbab和bdcbabb两个字符串，记为 和 ，我们要如何求它们的LCS呢？
既然已经说了是动态规划问题，我们就考虑如何从子状态转移过来。这有两种情形，第一种，如果两个序列最后一个元素相同，比如abecbab和bdcbabb，最后一个元素相同，所以它们的LCS长度就是abecba与bdcbab的LCS长度加上1。这是因为，
和 的任何公共子序列 去掉最后一个元素后，都是 和 的公共子序列，所以 的长度不会大于 。
如果最后一个元素不同，则LCS长度应为
，因为这时两个序列的最后一个元素不会同时出现在LCS中。
当然，我们还需要处理一下边界条件，即当
和 中至少有一个为空时，这时LCS的长度为0。于是综合一下，我们可以得到以下式子：
我们可以轻松地把它翻译成一个递归程序（我直接用Python写了）：
def lcs(s1,s2):if s1 == "" or s2 == "":return 0elif s1[-1] == s2[-1]:return lcs(s1[:-1], s2[:-1])+1else:return max(lcs(s1,s2[:-1]), lcs(s1[:-1],s2))
然而，稍微了解一点递归的原理的人都知道，直接这样写，必然引起时间、空间复杂度的爆炸。于是我们可以用记忆化的方法，并且传参时传索引而不是序列本身。
以下是HDU1159（LCS模板题）的AC代码：
#include <algorithm>#include <cstring>#include <iostream>using namespace std;const int MAXN = 505;char s1[MAXN], s2[MAXN];int dp[MAXN][MAXN];int lcs(int n1, int n2){if (dp[n1][n2] != -1)return dp[n1][n2];if (n1 == 0 || n2 == 0)dp[n1][n2] = 0;else if (s1[n1 - 1] == s2[n2 - 1])dp[n1][n2] = lcs(n1 - 1, n2 - 1) + 1;elsedp[n1][n2] = max(lcs(n1, n2 - 1), lcs(n1 - 1, n2));return dp[n1][n2];}int main(){while (cin >> s1 >> s2){memset(dp, -1, sizeof(dp));cout << lcs(strlen(s1), strlen(s2)) << endl;}return 0;}
当然，为了节约栈空间，我们也可以用递推的方法，代码也很简洁：
while (cin >> s1 >> s2){memset(dp, 0, sizeof(dp));int n1 = strlen(s1), n2 = strlen(s2);for (int i = 1; i <= n1; ++i)for (int j = 1; j <= n2; ++j)if (s1[i - 1] == s2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);cout << dp[n1][n2] << endl;}
这一算法的时间复杂度和空间复杂度均为
，如果用滚动数组（即只维护两个一维数组，只保留dp[i]和dp[i-1]中各项的值）可以把空间复杂度优化到 。
输出方案
例如，我们最终得到了这样一个二维数组：
我们知道，如果某个dp[i][j]比它左上方的值大1，且s1[i-1]==s2[j-1]（注意我这里用的是0-index所以要减1），说明可以选这个元素来增大LCS。于是我们可以用这样的策略：从右下角开始，如果有dp[i][j]==dp[i-1][j-1]+1则往左上走一格，如果同时还有s1[i-1]==s2[j-1]则将其加入；否则的话，它的左边或上边（根据公式）至少有一个与它相等，于是往与它相等的方向走一格；到左上角为止。这其实相当于把动态规划过程倒过来做了一遍。
最长公共子串
子串和子序列的区别在于，子串必须是连续的。求最长公共子串的长度和求最长公共子序列的长度的方法几乎一样，我们用dp[i][j]代表以
的第i个元素、 的第j个元素结尾的最长公共子串的长度。那么当s1[i-1]==s2[j-1]时递推公式与最长公共子序列的情形一致，但是当s1[i-1]!=s2[j-1]时会直接为0。这样写的话，因为我们不知道最长公共子串是以那两个元素结尾的，所以我们就需要枚举i、j来求最大值：
while (cin >> s1 >> s2){memset(dp, 0, sizeof(dp));int n1 = strlen(s1), n2 = strlen(s2), ma = 0;for (int i = 1; i <= n1; ++i)for (int j = 1; j <= n2; ++j)if (s1[i - 1] == s2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = 0;for (int i = 1; i <= n1; ++i)for (int j = 1; j <= n2; ++j)ma = max(ma, dp[i][j]);cout << ma << endl;}
得到的dp二维数组如下：
这个要输出答案就更简单了，找到使dp[i][j]最大的i或j，将对应的串从i或j处开始往前数dp[i][j]个元素，得到的子串就是最长公共子串。
变式
（CF1446B Catching Cheaters）
You are given two strings and representing essays of two students who are suspected cheaters. For any two strings CC, DD we define their similarity score as , where denotes the length of the Longest CommonSubsequenceof strings and .You believe that only some part of the essays could have been copied, therefore you're interested in theirsubstrings.
Calculate the maximal similarity score over all pairs of substrings. More formally, output maximal over all pairs , where is some substring of , and is some substring of .
If is a string, denotes its length.
A string is asubstringof a string if can be obtained from by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
A string is asubsequenceof a string if aa can be obtained from by deletion of several (possibly, zero or all) characters.
Pay attention to the difference between thesubstringandsubsequence, as they both appear in the problem statement.
You may wish to read the Wikipedia page about the Longest Common Subsequence problem.Input
The first line contains two positive integers and ( ) — lengths of the two strings and .
The second line contains a string consisting of nn lowercase Latin letters — string .
The third line contains a string consisting of mm lowercase Latin letters — string .Output
Output maximal over all pairs , where is some substring of , and is some substring of .Examplesinput
4 5
abba
bababoutput
5input
8 10
bbbbabab
bbbabaaaaaoutput
12input
7 7
uiibwws
qhtkxcnoutput
0
这个题其实就是最长公共子序列和最长公共子串的混合体，我们用dp[i][j]表示代表以
的第i个元素、 的第j个元素结尾的子串的最大 值。于是我们考虑转移，当s1[i-1]==s2[j-1]时， 可以从dp[i-1][j-1]转移过来， 值加2；当s1[i-1]!=s2[j-1]时，则是从dp[i-1][j]和dp[i][j-1]中的最大值转移过来， 值减1（但减到小于0时取0，因为可以不取）。
for (int i = 1; i <= n1; ++i)for (int j = 1; j <= n2; ++j)if (s1[i - 1] == s2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 2;elsedp[i][j] = max(max(dp[i - 1][j] - 1, dp[i][j - 1] - 1), 0);for (int i = 1; i <= n1; ++i)for (int j = 1; j <= n2; ++j)ma = max(ma, dp[i][j]);
Pecco：算法学习笔记（目录）
