다이나믹 프로그래밍 (동적 계획법)

큰 문제를 작은 문제로 쪼개서 해결하는 문제

• 작은 문제들에 중복이 있음: 다이나믹 프로그래밍 (중복을 제거하는게 목적, 메모이제이션)
• 작은 문제들에 중복이 없음: 분할 정복 (중복 없이 나누는게 목적)

두 가지 조건이 충족할 때 다이나믹 프로그래밍으로 해결 가능

• 작게 쪼갠 문제에 중복이 발생 함
• 작게 쪼갠 문제의 정답이 원래 문제의 정답과 연관 됨

해결 방법

• Top-down: 재귀 호출
• Bottom-up: 반복문

예시
피보나치 수: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n ≥ 2)

// O(2의n제곱)
int fibonacci(int n) {
  if (n <= 1) { return n; }
  else { fibonacci(n-1) + fibonacci(n-2) }
}

// 함수의 시간 복잡도 O(1) * N = O(N)
// Top-down 방식의 구현 - 재귀
int memo[100];
int fibonacci(int n) {
  if (n <= 1) { return n; }
  else {
    memo[n] = fibonacci(n-1) +   fibonacci(n-2);
    return memo[n];
  }
}
// Bottom-up 방식의 구현 - for문
int memo[100];
int fibonacci(int n) {
  memo[0] = 0;
  memo[1] = 1;
  for (int i=2; i<=n; i++) {
    memo[i] = memo[i-1] + memo[i-2]
  }
  return memo[n];
}