TSP 한 정점에서 출발하여 다른 정점을 각각 한번씩만 방문하고 다시 처음 정점으로 돌아오는 가장 짧은 경로를 결정하는 것. *음이 아닌 가중치가 있는, 방향성 그래프를 대상으로 함. 여행을 다 한 후 정점 1로 돌아오는 것으로 가정했을 때 아이디어는 dp[i][A]를 i에서 A에 속한 각 정점을 한번씩 거쳐서 정점 1로 가는 최단 경로의 길이라고 정의하는 것이다. 자 그럼 dp[1][A-{1}] = min(w[1][j] + dp[j][v-{1,j}) j는 2부터 나머지 정점 , w[i][j]는 i부터 j까지 거리. 무슨 말이냐면 정점 1에서 1를 제외하고 나머지 정점을 돌고 1로 돌아오는 것은? 1에서 다음 정점으로 이동한 가중치 + 다음 이동한 정점에서 출발하여 정점 1과 자신을 제외한 정점을 여행한..