問題解決レポート:hdu 1159 Common Subsequence(最長共通サブシーケンスLCS)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1159
Problem Description
与えられたシーケンスのサブシーケンスは、与えられたシーケンスであり、一部の要素(おそらくない)が漏れている.シーケンスX=厳密に増加するシーケンスが存在する場合、シーケンスXのサブシーケンスが与えられる....、ik>のインデックスは、すべてのj=1,2,...,k,xij=zjに対して使用される.例えばZ=インデックスシーケンス<1,2,4,6>のX= で行ないます。2つのシーケンスXとYが与えられ,問題はXとYの 最大長共通サブシーケンスの長さ。 プログラムはテキストファイルから入力します。ファイル内の各データセットには、指定したシーケンスを表す2つの文字列が含まれています。シーケンスは任意の数のスペースで区切られます。入力データは正しいです。各データのセットについて、プログラムは、個別の行から始まる最大長の共通サブシーケンスの長さを標準出力に印刷する。 
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
解題構想:基礎dp!2つの文字列の最長共通サブシーケンスの長さを求めると、dp[i][j]は文字列s 1の前i文字と文字列s 2の前j文字からなる最長共通サブシーケンスの長さを表し、s 1の第i文字とs 2の第j文字が等しい場合、dp[i][j]=dp[i-1][j-1]+1;そうでなければdp[i][j]=max(dp[i-1][j],dp[i][j-1])は、現在のdp[i][j]がs 1の前i-1文字とs 2の前j文字からなる最長共通サブシーケンスの長さであるdp[i-1][j]とs 1の前i文字とs 2の前j-1文字からなる最長共通サブシーケンスの長さであるdp[i][j-1]の両方の最大値を表す.dp解の核心は,現在の文字列に列挙されたある文字であり,いずれも別の文字列の各文字を列挙し,現在の最適解を記録し,最後にdp[len 1][len 2]を求めることがLCSの長さである.時間複雑度はO(nm)であった.
ACコード:

 1 #include
 2 using namespace std;
 3 const int maxn=1005;
 4 char s1[maxn],s2[maxn];int len1,len2,dp[maxn][maxn];
 5 int main(){
 6     while(cin>>(s1+1)>>(s2+1)){
 7         memset(dp,0,sizeof(dp));
 8         len1=strlen(s1+1),len2=strlen(s2+1);
 9         for(int i=1;i<=len1;i++){
10             for(int j=1;j<=len2;j++){
11                 if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]+1;
12                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
13             }
14         }
15         cout<endl;
16     }
17     return 0;
18 }

 
転載先:https://www.cnblogs.com/acgoto/p/8901945.html