Longest common subsequence問題：已知兩序列，求這兩個序列的最長公共子序列（不一定要連續(xù)）的長度。設(shè)二維數(shù)組dp[i][j]表示長度分別為i和j的序列A和B的LCS的最大長度，有狀態(tài)轉(zhuǎn)移方程：A[i]=B[j]時，dp[i][j]=dp[i-1][j-1]+1；A[i]≠B[j]時，dp[i][j]=max{dp[i-1][j],dp[i][j-1]}。
通過觀察發(fā)現(xiàn)，狀態(tài)dp[i][j]只與當(dāng)前行(dp[i][j-1])和上一行(dp[i-1][j]，dp[i-1][j-1])的狀態(tài)有關(guān)。這樣，我們可以設(shè)置2個一維數(shù)組c1[],c2[]，其中c1[]保存上一行的狀態(tài)信息，c2[]更新當(dāng)前行的狀態(tài)信息，更新完畢之后再將c2[]的狀態(tài)信息復(fù)制到c1[]中，循環(huán)結(jié)束后c1[length_B]就是所求LCS的最大長度，從而降低了空間需求。
1 #include <iostream>
2 using namespace std;
3
4 const int MAXN = 5001;
5 char str1[MAXN],str2[MAXN];
6 int i,j,len1,len2,c1[MAXN],c2[MAXN];
7
8 int main(){
9 while(scanf("%s",str1)!=EOF){
10 scanf("%s",str2);
11 len1=strlen(str1),len2=strlen(str2);
12 for(i=0;i<=len2;i++) c1[i]=0;
13 for(i=0;i<=len1;i++){
14 for(j=0;j<=len2;j++){
15 if(str1[i]==str2[j]) c2[j+1]=c1[j]+1;
16 else c2[j+1]=c2[j]>c1[j+1] ? c2[j]:c1[j+1];
17 }
18 for(j=1;j<=len2;j++) c1[j]=c2[j];
19 }
20 printf("%d\n",c1[len2]);
21 }
22 return 0;
23 }