hdu1159 LCS 템플릿 문제

제목 분석
원제 주소
가장 간단한 가장 긴 공통 서브시퀀스 (LCS) 문제의 템플릿 문제입니다.설명 안 해.
------------------------------------------------------------------------
상태 전환 방정식:
dp[i][j]=dp[i-1][j-1]+1                                 (a[i-1]==b[j-1])
dp[i][j]=max(dp[i-1][j],dp[i][j-1] )              (a[i-1]==b[j-1])
-------------------------------------------------------------------------
dp[i][j]는 a[i-1]와 b[j-1]의 LCS를 보존하고 있다.그래서 우리의 최종 결과는 dp[len1][len2](len1,len2는 각각 a,b 길이입니다. 아래 표시는 0부터 계산됩니다)
코드
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[505],b[505];
int dp[505][505];
int main()
{
    while(~scanf("%s%s",a,b))
    {
        int len1=strlen(a);
        int len2=strlen(b);
        for(int i=0;i<len1;i++)
            dp[0][i]=0;
        for(int i=0;i<len2;i++)
            dp[i][0]=0;
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        printf("%d
",dp[len1][len2]); } }

좋은 웹페이지 즐겨찾기