给定两个字符串S和T.求出这两个字符串最长的公共子序列的长度.

输入:

n=4

m=4

s="abcd"

t="becd"

 

输出:

3("bcd")

 

这类问题被称为最长公共子序列问题(LCS,Longest Common Subsequence)的著名问题.

                     max(dp[i][j]+1,dp[i][j+1],dp[i+1][j])   (s=t)

dp[i+1][j+1]=

                      max(dp[i][j+1],dp[i+1][j])                  (其他)

 

 

这个递推式可用O(nm)计算出来,dp[n][m]就是LCS的长度.

 

 

j\i	0	1{b}	2{e}	3{c}	4{d}
0	0	0	0	0	0
1{a}	0	0	0	0	0
2{b}	0	1	1	1	1
3{c}	0	1	1	2	2
4{d}	0	1	1	2	3

 

 

1 int n,m; 2 char s[MAX],t[MAX]; 3 int dp[MAX][MAX];   //DP数组 4  5 void solve() 6 { 7     for(int i=0; i<=n; i++){ 8         for(int j=0; j<=m; j++){ 9             if(s[i]==t[j]){10                 dp[i+1][j+1]=dp[i][j]+1;11             }12             else{13                 dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);14             }15         }16     }17     printf("%d\n",dp[n][w]);18 }

 

 

 

 

 

 

 

<<挑战程序设计竞赛>>读后感