9도 OJ 1042: Coincidence(DP)

2073 단어 dpC 언어OJ9도
시간 제한: 1초
메모리 제한: 32메가
특수 판제:아니오
제출: 2303
해결: 1241
제목 설명:
Find a longest common subsequence of two strings.
입력:
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
출력:
For each case, output k – the length of a longest common subsequence in one line.
샘플 입력:
abcd
cxbydz

샘플 출력:
2

출처:
2008년 상해교통대학 컴퓨터 연구 생기 시험 진제
아이디어:
동적 기획은 두 개의 지침을 설정하여 각각 처음부터 끝까지 두 개의 그룹을 검색하고 마지막에 얻는 것이 최대값이다.
동적 계획의 주요 방정식은 다음과 같습니다.if (a[i] == b[j])      res[i+1][j+1] = res[i][j]+1; else      res[i+1][j+1] = max(res[i+1][j], res[i][j+1]);
코드:
#include <stdio.h>
#include <string.h>
 
#define N 100
#define max(a, b) (((a)>(b)) ? (a) : (b))
 
int main(void)
{
    int na, nb, i, j;
    char a[N+1], b[N+1];
    int res[N+1][N+1];
 
    while (scanf("%s%s", a, b) != EOF)
    {
        na = strlen(a);
        nb = strlen(b);
        memset(res, 0, sizeof(res));
        for (i=0; i<na; i++)
        {
            for (j=0; j<nb; j++)
            {
                if (a[i] == b[j])
                    res[i+1][j+1] = res[i][j]+1;
                else
                    res[i+1][j+1] = max(res[i+1][j], res[i][j+1]);
            }
        }
        /*
        for (i=1; i<=na; i++)
        {
            for (j=1; j<=nb; j++)
            {
                printf("%d ", res[i][j]);
            }
            printf("
"); } */ printf("%d
", res[na][nb]); } return 0; } /************************************************************** Problem: 1042 User: liangrx06 Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/

좋은 웹페이지 즐겨찾기