고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.
문제가 배열을 최적으로 파괴/축소/병합(또는 유사)하도록 요청하는 경우 하위 세그먼트에서 동적 프로그래밍을 사용하여 문제를 해결해야 합니다.
dp[l][r] - 인덱스가 l에서 r까지인 하위 세그먼트에 대한 최적의 답을 구해 봅시다. 역학의 재계산은 작업에 따라 다르지만 다음과 같은 일반적인 아이디어가 있습니다.
1) 극단 요소 l과 r을 보십시오. 다른 방법으로 일치하거나 보완하는 경우 dp[l+1][r-1]을 통해 dp[l][r]의 값을 업데이트하는 것이 가능할 가능성이 높습니다. 그렇지 않으면 dp[l][r-1] 또는 dp[l+1[r]을 통해.
2) 세그먼트 [l;r]을 단일 구성으로 표현할 수 없는 경우가 종종 발생합니다. 그런 다음 이 하위 세그먼트의 모든 가능한 섹션을 두 부분으로 고려해야 합니다. 즉, 요소 k를 l에서 r-1까지 반복하고 dp[l][r]에서 dp[l][k] 및 dp[를 통해 다시 계산해야 합니다. k+1][r] . 더 작은 하위 세그먼트에서는 이러한 섹션도 분류되었으므로 실제로 하위 세그먼트 [l;r]를 두 부분뿐만 아니라 여러 부분으로 분할하는 옵션이 고려됩니다.