가장 길게 증가하는 서브 시퀀스에 대한 알고리즘을 이해할 수 없습니다.

Question

많은 온라인 리소스를 통해 문제가 어떻게 최적의 하위 구조를 가졌는지 알지만 헛된 것은 아닙니다. 더 작은 문제를 해결하여 솔루션을 얻는 방법을 이해할 수 없습니다. 이 경우 하위 문제.

해결책을 이해하는 데 도움이되는 설명이 있으면 감사하게 생각합니다.

예 요인 : 그래서

40의 계승 사실 (40), 우리는이 사실을 계산하여 용액을 얻을 수에 대해 (이하

는

지금까지, I는 최적의 서브 - 구조의 특성을 이해 39) * 40, 39,38 .... 2 ans에 대해 우리는 사실 (2)가 2임을 알고 있으므로 같은 방식으로 2에서 40까지 만들 수 있습니다.

는하지만 그 이후에 처리 할 수있는, 중복 하위 문제의 문제를 제외하고,

는 솔루션의 전체 설명은 좋은 것입니다 도와주세요 LIS의 측면에서 연관시킬 수 없습니다입니다.

감사합니다.

Answer 1

최적 하부 구조를 고려하기 전에 LIS의 경우 하위 문제가 무엇인지 결정해야합니다. 하위 문제 LIS[k]이 요소 a[k]에 정확하게 종료 초기 인덱스에서 가장 긴 증가 시퀀스의 길이를 찾을 수 있습니다 길이 N의 배열 a[N]에서

:이 정의를 사용하자.

여기의 차이를 이해하는 것이 중요합니다 : LIS[k]이 하지 첫 k 요소 LIS에 대한 해결책이다; 모든 i의 경우 인 경우 k까지 Max(LIS[i])입니다. 특정 엘리먼트에서 끝나는 최장 증가 서브 시퀀스의 길이입니다. 각 i 최대 N하는

• : 손이 정의에
  , 그것은 LIS 대한 해결책 구성 용이 1에
• 세트 LIS[i] (최악의 경우를 다수의 A는 하나의 서브 순서) j의 등이 a[i] > a[j] 및 LIS[j]+1 > LIS[i]에 포함 i-1, 최대 초기 요소에서
• 검색 LIS[j].

은 상기 알고리즘은 O (i)에서 아래의 모든 ij 초간 LIS[j]을 위해 하위 문제 LIS[i] 지정된 해결책에 대한 해결책을 구성 것을 쉽게 알 수있다. k-1 하위 문제에 대한 해답으로부터 k 문제에 대한 해를 구할 수 있기 때문에 문제는 최적의 하부 구조를가집니다.

참고 : 위의 내용은 이진 검색을 사용하여 더욱 최적화 할 수 있습니다. 하위 문제와 최적 하부 구조에 대한 추론은 동일합니다.