동적 계획 - LIS(Lead Exchange 서브시퀀스)

4273 단어
동적 계획 - LIS(Lead Exchange 서브시퀀스)
최대 증가 하위 시퀀스는 다음과 같은 동적 계획의 대표적인 문제입니다.
이미 알고 있는 서열 {a1,a2,...,an}에서 몇몇 그룹을 추출하여 새로운 서열 {ai1,ai2,......,aim}을 구성합니다. 그 중에서 아래 i1,i2,......im는 점차적으로 증가한다. 즉, 새로운 수열의 각 수 간에 여전히 원수열의 선후 순서를 유지한다. 그러면 우리는 새로운 서열 {ai1,ai2,...,aim}을 원 서열의 하위 서열이라고 부른다.하위 서열에서, ix>iy를 표시할 때,ix>aiy를 표시하면, 우리는 이 하위 서열을 원래 서열의 점증 하위 서열이라고 부른다.최장 증자 서열 문제는 주어진 원 서열에서 최장 증자 서열의 길이를 구하는 것이다.
서열 {a1,a2,...,an}이 있습니다. 서열의 가장 긴 점차적인 서열 길이를 구합니다.점차적인 추측에 따라 우리는 F[i]로 점차적인 서열이ai로 끝날 때 가장 긴 길이를 대표한다.i가 작으면 F[1]=1과 같은 값을 직접 얻기 쉽다.그렇다면 어떻게 이미 구한 F[i]값으로 뒤의 값을 미룰 수 있습니까?가령 F[1]에서 F[x-1]까지의 값이 모두 확정되었다고 가정하면 ax로 끝나는 점증자 서열은 길이가 1인 경우를 제외하고 다른 상황에서 ax는ai(i예를 들어 서열 {1,4,3,2,6,5}의 가장 긴 증자 서열 길이의 모든 F[i]는 다음과 같다.
F[1] (1)
F[2](4)
F[3](3)
F[4](2)
F[5](6)
F[6](5)
1
2
2
2
3
3
요약하면 가장 긴 증자 서열을 구하는 추이 공식은 다음과 같다.
F[1] = 1;
F[i] = max{1,F[j]+1|aj
우리는 추이 공식에 근거하여 알고리즘을 실현할 수 있다
#include 
using namespace std;
const int MAXSIZE = 10;
const int MIN = 0;
int arr[] = { 1, 4, 3, 2, 6, 5 };
int F[MAXSIZE];
int main()
{
    int maxLen = MIN;
    memset(F, 0, MAXSIZE);
    F[0] = 1;
    for (int i = 1; i < 6; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j] && maxLen < F[j])
            {
                maxLen = F[j];
            }
        }

        F[i] = maxLen + 1;
    }

    for (int k = 0; k < 6; k++)
        cout << F[k] << ' ';
    cout << endl;
}

posted on
2015-12-09 20:32 RunningSnail 읽기 (
...) 설명(
...) 모음 편집
전재 대상:https://www.cnblogs.com/tgycoder/p/5034131.html
Finder가 원격 환경을 확인할 수 있는 파일
kotlin을 사용한 간결하고 유형이 안전한 스크립팅

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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