Naive하게 풀면, 경찰 a, b에 순차적으로 사건을 맡겨보면서 recursive 하게 풀 수 있다. 이때, 시간 복잡도는 O(2^N)이다. 그러나, sup-problem이 반복적으로 나타나기 때문에, Dynamic Programming으로 개선할 수 있다.
dp[a][b]에 경찰차 A, B 가 사건 a, b를 맡고 있을 때 가능한 최소 값을 저장한다.
solve( a, b ):
dp[a][b] = min( 경찰차 1을 w로 움직이는 비용 + solve( w, b ),
경찰차 2를 w로 움직이는 비용 + solve( a, w) )
dp[w+1][w+1]
시간 복잡도는 O(N^2) 이다.
Bottom-Up 방식으로도 풀 수 있을 것 같지만, dp를 계산하고, 경로를 추적하는 함수가 더 복잡할 것 같다.