[알고리즘] Dynamic Programming - 동적프로그래밍

* 동적프로그래밍(Dynamic Programming)이란?  // 분할정복알고리즘과의 비교

 - 분할정복식 알고리즘 설계법은 하향식 해결법으로 나누어진 문제가 독립적인 문제를 해결하는데 적합하다.
  > 피보나치의 알고리즘을 분할정복식으로 구현하면, 알고리즘을 실행하면서 같은 계산을 한 번 이상하는 결과를     유발한다. 따라서 분할정복 알고리즘에 적용하기 부적합하다.
 - 동적 프로그래밍은 상향식 해결법으로 분할정복식과 같이 문제를 나눈 후에 나누어진 하위 문제들을 해결한다.
  > 문제를 해결할시 하위에서 풀은 값이 상위의 문제를 해결하는데 필요하면, 반복계산없이 하위 결과를 가져와
    사용한다.
 

* 동적프로그래밍 설계 전략

 - 문제의 한 부분을 더 작은 하위 문제들의 부분으로 분할한다.
 - 작은 하위 문제들의 실례를 먼저 해결하고, 그 결과값을 table을 이용해 저장한다.
 - 상위 문제를 해결할때 하위 문제의 결과값이 필요하면 table에서 값을 불러와 사용한다.


* 동적프로그래밍 설계시 따라야할 과정

 1. 우리가 풀고자 하는 문제의 일반화된 형(form)을 정의한다. 즉, 문제를 나눈다.
 2. 괄호에 나온 특징을 고려하여 이 문제를 풀기 위한 풀이 순서를 정한다.
    (어떠한 한 문제는 순서에서 앞선 문제들에 대한 결과값을 사용하여 해결이 가능할 것이다.) 
 3. 문제 풀이 순서의 처음에 있는 문제들은 자명한 해법들을 가지고 있어야 한다.
 4. 문제 풀이 순서에 맞게 문제를 해결하며 Table에 저장을한다.
     (상위 문제를 풀때 하위 문제에 의해 해결된 결과값을 필요로하면 Table에서 가져온다.)
 5. 목록의 마지막 문제는 본래의 문제여야 한다.