[C언어/DP] 9251 : LCS

#include<stdio.h>
#define MAX 1005

int max(int a,int b){
	return a>=b?a:b;
}
int main(void){
	int i,j;
	int dp[MAX][MAX]={0,};
	char s1[MAX],s2[MAX];
	scanf("%s %s",s1+1,s2+1);
	
	for(i=1;s1[i];i++){
		for(j=1;s2[j];j++){
			dp[i][j]=max(max(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]+(s1[i]==s2[j]));
		}
	}
	printf("%d",dp[i-1][j-1]);
	return 0;
}

 

http://melonicedlatte.com/algorithm/2018/03/15/181550.html

 

다음 블로그를 참고해서 풀었다.

 

dp[i][j]=max(max(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]+(s1[i]==s2[j])); 

이 코드에서 마지막 부분을 if문 처리를 안하고 저렇게 간결하게 작성할 수도 있었다.

 

for(i=1;s1[i];i++)

조건문에 이렇게 표현한 것도 간결해서 좋았다.