출처: 쉽게배우는 알고리즘(한빛미디어)

Dynamic Programming (동적프로그래밍)

큰 문제를 작은 문제로 나누어 푸는 방법이라 할 수 있음

Dynamic,동적이라는 단어와는 상관없는 방법. 이름으로 오해하지말 것

다음 속성을 만족하는 경우 - DP로 해결

• Optimal Substructure : 문제의 정답을 작은 문제에서 구할 수 있음
  이 속성은 문제의 크기에 상관없이 작은 문제의 답이 일정함
  ex) 피보나치 1 1 2 3 5 8 13 21
  $f(n) = f(n-1)+f(n-2)$
  n번째 수를 구하는 것은 n-1과 n-2번째 수를 구하는 것으로 구할 수 있음
  (n = 4일때, f(2)의 값) == (n = 100일때, f(2)의 값)

• Overlapping Subproblem : 큰 문제는 작은문제로 분해됨.
  그리고 두 문제모두 같은 방식으로 해결가능
  재귀로 구현할시, 지나친 중복이 발생함
  ex) 피보나치 n = 8 구하기.
  

→ 작은문제 1번만 풀기! - Memoization 사용

• Memoization : 해당 문제의 정답을 구하고 배열에 저장
  ex) Memoization사용한 피보나치
  

풀이방법

top-down(문제→작은문제), bottom-up(작은문제→문제) 방식 사용가능
변수의 개수 = 메모하는 배열 개수
작은 문제로 나누고 수식을 사용하여 풀이