동적 계획 - 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
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.