最長公共子序列（poj1458）

問題簡略描述：

給定兩個字元串，尋找其最長的公共的子序列（非連續）；

輸入資料

多組輸入兩個長度不超過200的字元串，表示兩個序列 兩個字元串用空格隔開

輸入樣例

abcfbc abfcab

programming contest

abcd mnp

輸出樣例

4

2

解(HU)題(SHUO)思(BA)路(DAO)

用兩個字元數組a[]和b[]存儲字元串，a[i]和b[j]分别表示a中的第i+1和j+1個字元

作為蒟蒻 第一眼就想着對每一個字元串暴力枚舉 然鵝寫着寫着發現複雜度能達到200^200，果斷放棄暴力，采取動态規劃思想，不難想出 其遞推關系式為：

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]);
           

參考程式：

#include<bits/stdc++.h>
using namespace std;
int dp[300][300]={0};
char a[300]={NULL},b[300]={NULL};
int main(){
	while(scanf("%s%s",a,b)!=EOF){//循環輸入
	int i,j,m=strlen(a),n=strlen(b);
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			if(a[i]==b[j]){
			dp[i][j]=dp[max(i-1,0)][max(j-1,0)]+1;//使用max(i-1,0)是為防止角标小于0
			}
			else dp[i][j]=max(dp[max(i-1,0)][j],dp[i][max(j-1,0)]);
		}
	}
	cout<<dp[m-1][n-1]<<endl;
	memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(dp,0,sizeof(dp));//清空
	}

}