uvaoj 10405 Longest Common Subsequence 최장 공통 하위 시퀀스

1862 단어 동적 기획uvaoj
uvaoj 10405 Longest Common Subsequence 
가장 긴 공공 서열, 가장 간단하고 가장 기본적인 dp, 모두가 dp를 배울 때 이 가장 긴 공공 서열을 먼저 말해야 한다고 믿습니다.LCS라고도 합니다.
상태는 간단합니다. dp[i][j]는 첫 번째 문자열의 전 i자 문자로 구성된 문자열과 두 번째 문자열의 전 j자 문자로 구성된 문자열의 가장 긴 공통 서열의 길이를 나타냅니다.
이동은 매우 간단하고 두 가지 상황으로 나뉘는데 s1[i]이 s2[j]와 같을 때 dp[i][j]=dp[i-1][j-1]+1;같지 않을 때 dp[i][j]=max(dp[i-1][j], dp[i][j-1]).
이 제목의 구덩이는 문자열 중간에 빈칸이 있을 수 있으므로 순서대로 한 줄로 읽어야 한다.
코드 입력:
/*************************************************************************
	> File Name: uvaoj10405.cpp
	> Author: gwq
	> Mail: [email protected] 
	> Created Time: 2014 10 28      10 45 26 
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())

using namespace std;
typedef set si;
typedef vector vi;
typedef map mii;
typedef long long ll;

#define N 3010

string s1, s2;
int dp[N][N];

int main(int argc, char *argv[])
{
	//          
	while (getline(cin, s1) && getline(cin, s2)) {
		int l1 = s1.length();
		int l2 = s2.length();

		clr(dp, 0);
		for (int i = 1; i <= l1; ++i) {
			for (int j = 1; j <= l2; ++j) {
				if (s1[i - 1] == s2[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[l1][l2]);
	}

	return 0;
}
소프트 UI 대시보드 - 무료 Jinja 템플릿
★Webpack 6회차 - 로더의 도입

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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