동적 프로그래밍의 패턴 - 2

고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.

문제가 배열을 최적으로 파괴/축소/병합(또는 유사)하도록 요청하는 경우 하위 세그먼트에서 동적 프로그래밍을 사용하여 문제를 해결해야 합니다.

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]를 두 부분뿐만 아니라 여러 부분으로 분할하는 옵션이 고려됩니다.
 

고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.

문제에서 순열의 존재를 확인해야 하거나 일치하는 순열의 수 또는 이와 유사한 것을 찾아야 하는 경우 동적 하위 집합 프로그래밍 사용을 고려해야 합니다.

기본 매개변수는 순열에 이미 포함된 요소와 포함되지 않은 요소를 표시하는 비트마스크입니다. 마지막으로 포함된 요소를 나타내는 두 번째 매개변수도 종종 필요합니다.

종종 순열은 그래프의 경로 컨텍스트에서 볼 수 있습니다. 따라서 고전적인 예인 해밀턴 경로 문제를 살펴보겠습니다.
해밀턴 경로는 그래프의 각 정점을 정확히 한 번 통과하는 단순 경로입니다. 길이 n의 순열로 간단하게 표현할 수 있습니다. 여기서 n은 정점의 수입니다. 이 순열 내의 순서는 이 경로의 꼭지점을 통과하는 순서를 나타냅니다.

그래프에서 Hamiltonian 경로의 존재를 확인하기 위해 역학을 시작하겠습니다.
초기 값은 dp[2ⁱ][i] = true이고 나머지는 false입니다. 즉, 정점에서 시작하는 빈 경로가 항상 있음을 의미합니다.
dp[mask][last] 값이 true이면 "경로 확장"이라는 의미에서 앞으로 전환합니다. 즉, 우리는 마스크에서 0으로 표시된 정점의 수를 찾고(아직 도중에 방문하지 않았음) 마지막에서 이 정점까지의 가장자리가 있는지 확인합니다(경로는 반드시 기존 가장자리로 확장). 즉, dp[mask | 2^k][k] = dp[mask][last] = true AND mask & 2^k = 0(정점 k는 아직 방문하지 않았음) 그리고 마지막에 에지가 있음 -> 케이.
궁극적으로, 모든 비트 마스크와 마지막 정점의 매개 변수에 대한 dp에 참 값이 있는 경우 해밀턴 경로가 존재합니다.