最長公共子序列

點擊打開鏈接時間限制：3000?ms ?|? 內存限制：65535?KB 難度：3 描述

咱們就不拐彎抹角了，如題，需要你做的就是寫一個程序，得出最長公共子序列。
tip：最長公共子序列也稱作最長公共子串(不要求連續(xù))，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。 輸入

第一行給出一個整數(shù)N(0<N<100)表示待測數(shù)據(jù)組數(shù)
接下來每組數(shù)據(jù)兩行，分別為待測的兩組字符串。每個字符串長度不大于1000.

輸出

每組測試數(shù)據(jù)輸出一個整數(shù)，表示最長公共子序列長度。每組結果占一行。

樣例輸入

2 asdf adfsd 123abc abc123abc

樣例輸出

3 6 這也是一個動態(tài)規(guī)劃問題，下面是動態(tài)轉移方程： ? dp[i][j]=dp[i-1][j-1]+1; (str1[i-1]==str2[j-1]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); ?(str1[i-1]!=str2[j-1]) AC代碼： #include<stdio.h> #include<string.h> #define max(a,b) a>b?a:b; int dp[1010][1010]; char str1[1010],str2[1010]; int main() {int len1,len2,i,j,n;scanf("%d",&n);while(n--){scanf("%s",str1);scanf("%s",str2);len1=strlen(str1);len2=strlen(str2);memset(dp,0,sizeof(dp));for(i=1;i<=len1;i++)for(j=1;j<=len2;j++){ if(str1[i-1]==str2[j-1])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}printf("%d\n",dp[len1][len2]);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 36 最长公共子序列 dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。