动态规划基础（二）最长公共子序列 LCS

讲解求两个串中最长的公共的子序列长度或输出子序列等
poj1458

题目大意

给定两个字符串，要求输出两个字符串中最长公共子序列长度

思路

我们定义$a[i][j]$为，当字串$str1$到$i$位置，字串$str2$到$j$位置时，最长公共子串的长度，我们有如下关系式：
$if$ $str1[i]==str2[j],a[i][j]=a[i-1][j-1]+1$
$else$ $a[i][j]=max(a[i-1][j],a[i][j-1]$
最后打印即可

ACcode

#include<bits/stdc++.h>using namespace std;int a[1005][1005];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);string str1, str2;while (cin >> str1 >> str2) {int len1 = str1.size();int len2 = str2.size();for (int i = 0;i <= len1;i++)a[i][0] = 0;for (int j = 0;j <= len2;j++)a[0][j] = 0;for (int i = 1;i <= len1;i++) {for (int j = 1;j <= len2;j++) {if (str1[i - 1] == str2[j - 1])a[i][j] = a[i - 1][j - 1] + 1;else a[i][j] = max(a[i - 1][j], a[i][j - 1]);}}cout << a[len1][len2] << '\n';}return 0;
}