고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.
문제에서 순열의 존재를 확인해야 하거나 일치하는 순열의 수 또는 이와 유사한 것을 찾아야 하는 경우 동적 하위 집합 프로그래밍 사용을 고려해야 합니다.
기본 매개변수는 순열에 이미 포함된 요소와 포함되지 않은 요소를 표시하는 비트마스크입니다. 마지막으로 포함된 요소를 나타내는 두 번째 매개변수도 종종 필요합니다.
종종 순열은 그래프의 경로 컨텍스트에서 볼 수 있습니다. 따라서 고전적인 예인 해밀턴 경로 문제를 살펴보겠습니다.
해밀턴 경로는 그래프의 각 정점을 정확히 한 번 통과하는 단순 경로입니다. 길이 n의 순열로 간단하게 표현할 수 있습니다. 여기서 n은 정점의 수입니다. 이 순열 내의 순서는 이 경로의 꼭지점을 통과하는 순서를 나타냅니다.
그래프에서 Hamiltonian 경로의 존재를 확인하기 위해 역학을 시작하겠습니다.
초기 값은 dp[2i][i] = true이고 나머지는 false입니다. 즉, 정점에서 시작하는 빈 경로가 항상 있음을 의미합니다.
dp[mask][last] 값이 true이면 "경로 확장"이라는 의미에서 앞으로 전환합니다. 즉, 우리는 마스크에서 0으로 표시된 정점의 수를 찾고(아직 도중에 방문하지 않았음) 마지막에서 이 정점까지의 가장자리가 있는지 확인합니다(경로는 반드시 기존 가장자리로 확장). 즉, dp[mask | 2k][k] = dp[mask][last] = true AND mask & 2k = 0(정점 k는 아직 방문하지 않았음) 그리고 마지막에 에지가 있음 -> 케이.
궁극적으로, 모든 비트 마스크와 마지막 정점의 매개 변수에 대한 dp에 참 값이 있는 경우 해밀턴 경로가 존재합니다.