LIS(최장 시퀀스) 및 LCS(최장 공통 서브) 요약

LIS(최장 증가 하위 시퀀스) 및 LCS(최장 공통 하위 시퀀스)의 요약
최대 공통 하위 시퀀스(LCS): O(n^2)
두 개의 for 순환은 두 문자열을 위치에 따라 일치하게 한다. i in range(1,len1) j in range(1,len2) s1[i-1] = s2[j-1], dp[i] [j] = dp[i-1] [j-1] + 1;s1[i - 1] != s2[j - 1], dp[i][j] = max (dp[i - 1][j], dp[i][j - 1]); 초기화: dp[i][0] = dp[0][j] = 0;
위조 코드:

    dp[maxn1][maxn2];
    s1[maxn1],s2[maxn2];
    p[maxn1][maxn2][2];
    //init
    for i in range(0, len1):
        dp[i][0] = 0;
    else:;
    for i in range(0, len2):
        dp[0][i] = 0;
    else:;

    for i in range(1, len1):
        for j in range(1, len2):
            if s1[i] == s2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1;
                p[i][j][0] = i - 1;
                p[i][j][1] = j - 1;
            else:
                if dp[i - 1][j] > dp[i][j - 1]:
                    dp[i][j] = dp[i - 1][j];
                    p[i][j][0] = i - 1;
                    p[i][j][1] = j;
                else:
                    dp[i][j] = dp[i][j - 1];
                    p[i][j][0] = i;
                    p[i][j][1] = j - 1;
        else:;
    else:;
    return dp[len1][len2];
    //path    
    function print_path(len1, len2):
        if (dp[len1][len2] == 0)
            return;
        printf_path(p[len1][len2][0], p[len1][len2][1]);
        if s1[len1] == s2[len2]:
            printf:s1[len1];
    end function;

제목: UVA - 531Compromise UVA - 10066The Twin Towers UVA - 10192Vacation uva10405 - Longest Common Subsequence
LIS(Lead Exchange 하위 시퀀스): O(n^2)
왼쪽에서 오른쪽으로 i 길이를 구하는 서열의 가장 긴 증자 서열의 길이, 상태 이동 방정식: dp[i]=Max(dp[j]+1);i in range(1, len); j in range(1, i - 1);
위조 코드

    s[maxn],dp[maxn];

    for i in range(1, len):
        dp[i] = 1;

    int maxlen = 1;
    for i in range(2, len):
        for j range(1, i - 1):
            if s[i] > s[j]:
                dp[i] = Max(dp[i], dp[j] + 1);
        else:
            maxlen = max(maxlen, dp[i]);
    else:;
    return maxlen;
    //path  
    function print_path(maxlen):
        if maxlen == 0:return;

        for i in range(1, len):
            if dp[i] == maxlen:
                print_path(maxlen - 1);
                printf:s[i];
    end function;

제목: UVA - 10599Robots(II)
최대 증가 하위 시퀀스 O (n * logn)
아니면 왼쪽에서 오른쪽으로 i의 길이를 구하는 서열의 가장 긴 점증자 서열의 길이입니다. 그러나 dp[j]의 최대치를 다시 확정할 때 한 층의 순환으로 찾아야 합니다.이렇게 하면 비교적 효과가 없다.만약 앞의 i 길이 서열에 나타난 가장 긴 증자 서열을 저장한다면, 찾을 때 2분으로 O (logn) 의 복잡도를 실현할 수 있다.이전 i 서열의 가장 긴 증자 서열을 LIS 그룹으로 저장하고 i번째 숫자를 찾을 때num[i]>LIS[top]를 가정하면 LIS[++top]=num[i];dp[i] = top;num[i]=LIS[top]를 가정하면 dp[i]=top;num[i]제목: UVA - 10534Wavio Sequence
위조 코드

    dp[maxn], LIS[maxn], s[maxn];
    top = 0;
    LIS[top++] = s[1];

    int maxlen = 1;
    for i in range(2, len):
        if s[i] > LIS[top]:
            LIS[++top] = s[i];
            dp[i] = top + 1;
        else if s[i] == LIS[top]:
            dp[i] = top + 1;
        else:
            k = lower_bound(LIS.begin(), LIS.end(), s[i]) - LIS.beign();
            LIS[k] = s[i];
            dp[i] = k + 1;

        maxlen = max(maxlen, dp[i]);
    else:;
    return maxlen;

최대 공통 하위 시퀀스 O (n * logn)
요구열 자체에 같은 숫자나 자모가 나타나지 않는다.첫 번째 문자열을 매핑합니다(증가 순서).그리고 두 번째 문자열은 위의 첫 번째 문자열에 따라 등가로 비추어 문제를 LCS에서 LIS로 전환시킨다.예: 직렬 1:2 4 3 5 6 매핑: 1 2 3 4 5 직렬 2:3 2 6 8 10 등가 매핑: 3 1 5 0
제목: uva10635Prince and Princess
판권 성명: 본 블로그의 오리지널 글, 블로그는 동의 없이 전재할 수 없습니다.

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

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

Java 기본 사용법 요약 (2)

StringBuilder 또는 StringBuffer를 사용할 때 append () 방법으로 텍스트를 추가하고 toString () 방법으로 연결된 전체 텍스트를 가져올 수 있습니다 3. Iterator를 사용합니다...

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

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

LIS(최장 시퀀스) 및 LCS(최장 공통 서브) 요약

좋은 웹페이지 즐겨찾기