Dynamic Programming의 Concept

Dynamic Programming은 자주 사용되는 기법으로 그 Concept을 아주 간략하게 설명하면, Optimal solution을 찾는 Problem에서 이를 Sub-problem으로 잘게 나누어 각각의 Optimal Solution을 구한 후, 이를 합쳐 최종적으로 Optimal Solution을 구하는 방법이다.


예를 들어보면, 간단하다.

Find the shortest route : u -> v

이 문제를 Sub-problem인 u -> w  (p1) 와 w -> v (p2) 로 나눈다.

그리고 u->w와 w->v 각각의 optimal solution을 찾은 후, 이를 합치면 최종적인 optimal solution이 된다.
 

+ 그런데, 만약에 문제가 살짝 바뀌어서 이렇게 되면 어떻게 될까?

Find the longest route : u -> v

 solution은 u -> z -> w -> v 가 되겠지만, Dynamic Programming으로 이를 찾으려면 Sub-problem을 어떻게 나뉘어야 할까?



이처럼 Dynamic Programming이 어디에서나 쓰일 수 있는 것은 아니다.