最长公共子序列(HDU-1159)
注意子序列和子串的区别
用\(dp[i][j]\)表示序列\(X\)前\(i\)项和序列\(Y\)的前\(j\)项的最长子序列的长度
当\(x[i] = x[j]\)时,\(dp[i][j] = dp[i - 1][j - 1] + 1\);
当\(x[i] \neq y[j]\)时,\(dp[i][j] = max(dp[i - 1][j]), dp[i][j - 1]\)
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e4;
int dp[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string a, b;
while (cin >> a >> b)
{
a = '.' + a;
b = '.' + b;
for (int i = 1; i < a.size(); i ++ )
for (int j = 1;j < b.size(); j ++ )
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
cout << dp[a.size() - 1][b.size() - 1] << '\n';
}
return 0;
}
标签:include,int,笔记,序列,线性,未整理,dp,size
From: https://www.cnblogs.com/Panmaru/p/17053215.html