HDU 1159 Common Subsequence 최장 공통 하위 시퀀스(LCS)

HDU 1159

Common Subsequence

최대 공통 하위 시퀀스(LCS)

제목 링크

HDU1159

해석하다

이것은 《알고리즘 경연의 입문에서 진급까지》의 예제인데, 표절서의 해설이 아니다.

문제 해결 코드

일반판

#include
#define ll long long
using namespace std;
const int MAXN = 6000;
const int MAXM = 6000;
char s1[MAXN];
char s2[MAXM];
int dp[MAXN][MAXM];
int n,m;
int solve()
{
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (s1[i] == s2[j])
			{
				dp[i][j] = dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	return dp[n][m];
}
int main()
{
	while (~scanf("%s%s", s1+1, s2+1))
	{
		n = strlen(s1+1);
		m = strlen(s2+1);
		printf("%d
", solve());;
	}
	return 0;
}

스크롤 배열

이거 1차원으로 하면 좀 복잡한 것 같아서 2차원으로 했어요.emmm가 배로 늘어나면 공간 차이가 많지 않아서 문제가 크지 않다고 생각합니다.

#include
#define ll long long
using namespace std;
const int MAXN = 6000;
const int MAXM = 6000;
char s1[MAXN];
char s2[MAXM];
int dp[2][MAXM];
int n,m;
int solve()
{
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (s1[i] == s2[j])
			{
				dp[i%2][j] = dp[(i-1)%2][j-1]+1;
			}
			else
			{
				dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]);
			}
		}
	}
	return dp[n%2][m];
}
int main()
{
	while (~scanf("%s%s", s1+1, s2+1))
	{
		n = strlen(s1+1);
		m = strlen(s2+1);
		printf("%d
", solve());;
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

49일차 - 2022.04.20

Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다