최적해 문제를 동적 계획법으로 구하는 순서

1.  완전 탐색 알고리즘 작성.

주어진 최적해 문제를 완전 탐색 알고리즘으로 해결하는 코드를 작성한다.

2. 부분 문제의 정의를 변경.

부분 문제가 현재까지 거쳐 온 전체 답을 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 값을 반환하도록 부분 문제의 정의를 바꾼다.

 

기존의 부분 문제가 현재 단계의 문제를 해결한 결과를 변수에 누적하여 다음 단계로 재귀 했다면, 현재 단계를 해결한 값에 다음 단계의 값(재귀 호출) 들을 더한 값을 반환하는 것이다.

 

이전에 작성한 Triangle path 문제를 예로 들면, 완전 탐색으로 구현한 경우 현재 단계의 점수인 try[y][x] 를 sum 에 누적해 그 값으로 다음 선택을 재귀호출 했다.

 

path(y, x, sum) = max(path(y+1,x,sum+tri[y][x]), path(y+1,x+1,sum+tri[y][x]))

 

이를 아래와 같이 변경해 각 단계에서의 점수 try[y][x] 에 다음 선택에 대한 재귀 호출의 반환값을 더해 반환하는 형태로 변경한다. 최적 부분 구조가 성립하는 문제이기 때문에 어떤 부분 문제에서든 다음에 있을 선택(항상 최적해이다.)만 고려하면 되는 것이다.

 

path(y, x) = tri[y][x] + max(path(y+1, x), path(y+1, x+1))

3. 재귀 호출의 입력 정리하기.

재귀 호출의 입력에 이전 단계 선택에 대한 정보가 있다면 필요한 것만 남기고 줄인다. 이를 통해 중복되는 부분 문제를 많이 만들게 되는데, 입력의 종류가 줄어들수록 많은 부분 문제가 중복되고 메모이제이션을 최대한 활용할 수 있게 된다.

4. 재귀 호출의 입력을 메모이제이션이 쉽도록 조절하기.

재귀 호출의 입력이 배열 혹은 문자열이라면 가능한 적절히 변환해 메모이제이션을 적용하기 쉽도록 한다.

5. Memoization 적용하여 마무리.