| 동적프로그래밍 개념 | 동적프로그래밍 사례 | 분할정복과 동적프로그래밍 비교 |

동적 프로그래밍과 분할 정복 비교

■ 동적 프로그래밍 해결 방법은 분할 정복과 유사

• 분할 정복에서는 분할되는 소문제가 소로 독립적이어서 소문제를 다시 순환적으로 풀어 그 결과를 합치면 된다.
• 동적 프로그래밍에서는 소문제가 독립적이지 않아서, 다시 말해서 분할된 소문제간에 중복되는 부분이 있어서 이를 분할 정복 방법으로 풀면 똑같은 소문제를 여러 번 반복해서 풀어야 하는 경우가 발생
• (예) 피보나치 수 fn = fn-1 + fn-2, n >= 2의 계산에 분할 정복 방법을 적용한다면
  f10 계산시에 f9와 f8을 계산해야 하는데 f9 계산시에 다시 f8을 구해야 하므로 f8은 중복해서 계산된다. 동적 프로그래밍에서는 소문제의 해를 표에 저장해 놓으므로 f8은 한 번만 계산하여 그 결과를 표에 저장해 놓고 필요할 때 이 표에서 그 값을 꺼내오면 된다.

■ 동적 프로그래밍과 분할 정복 비교