POJ1458 Common Subsequence

あの有名な最長共通部分列問題。

典型的な問題。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main(){
	
	char a[2000],b[2000];
	
	while(cin>>a>>b){
		
		int dp[1001][1001] = {0};
		
		int alen = strlen(a);
		int blen = strlen(b);
		
		for(int i = 0;i < alen;i++){
			for(int j = 0;j < blen;j++){
				
				if(a[i] == b[j]){
					dp[i+1][j+1] = dp[i][j]+1;
				}else{
					dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
				}
				
			}
		}
		
		printf("%d\n",dp[alen][blen]);
	}
	
	return 0;
	
}