动态规划基础（二）最长公共子序列 LCS
讲解求两个串中最长的公共的子序列长度或输出子序列等
poj1458
题目大意
给定两个字符串，要求输出两个字符串中最长公共子序列长度
思路
我们定义 a [ i ] [ j ] a[i][j] a[i][j]为，当字串 s t r 1 str1 str1到 i i i位置，字串 s t r 2 str2 str2到 j j j位置时，最长公共子串的长度，我们有如下关系式：
i f if if s t r 1 [ i ] = = s t r 2 [ j ] , a [ i ] [ j ] = a [ i − 1 ] [ j − 1 ] + 1 str1[i]==str2[j],a[i][j]=a[i-1][j-1]+1 str1[i]==str2[j],a[i][j]=a[i−1][j−1]+1
e l s e else else a [ i ] [ j ] = m a x ( a [ i − 1 ] [ j ] , a [ i ] [ j − 1 ] a[i][j]=max(a[i-1][j],a[i][j-1] 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;
}