Bitonic Cycle1 [코드트리] 8 - DP, Bitonic Cycle 바이토닉 사이클반드시 한번씩 방문해야하는 상태일때만 [i][j] 가능-> 간선 스킵은 cost가 0이 되는거라 pos 안써도 i-> 한번 스킵하면 영원히 다시 보지 않는다면 스킵 옵션 있을때도 가능정점 자체를 고르지 않고 지나가는 상태면 마지막 방문 위치를 스킵하게 돼서 pos가 필요함-> 현재 DP 상태가 완전히 확정된 상태가 아닌 경우-> TSP가 이런 상태라고 이해하면 된다. 다시말해 바이토닉 사이클은 일종의 TSP의 특수한 경우인 것 같다?? dp [i][j] [option] = max(i,j) 까지 dp 값을 확정했을 때 option 은 추가 조건 제약을 보고 추가하기(주로 skip 수)초기값은 dp[0][1] = 0~1 사이 가중치 계산 or 적절한 초기값 i, j 는 항상 i 가능한 상태는 .. 2026. 6. 29. 이전 1 다음