동적 계획법(Dynamic Programming)의 정의
어떤 문제가 반복적이고 최적 하위구조로 이루어질 때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법
최하위 구조(Optimal Substructur)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을 때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다.
분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데 반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할 정복은 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만, 동적 계획법은 이전 단계의 답에 의존적이다. 그래서 한번 푼 적 있는 문제는 다시 푸는 일이 없도록 테이블 등에 저장해둔다.
동적 계획법(Dynamic Programming) 알고리즘
1) 문제를 부분 문제로 나눈다.
2) 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다.
3) 테이블 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.
동적 계획법의 활용
1) 피보나치 수열 (Fibonacci Sequence)
피보나치 수열은 다음과 같이 정의할 수 있다. 
이것을 코드로 옮기면 아래와 같다
int Fibonacci(int n) {
if ( n > 1 )
return Fibonacci(n - 1) + Fibonacci(n - 2);
else if ( n == 1 )
return 1;
else
return 0;
}
[참고]
