1. 개념 정리

• 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고,
  과거에 구한 값을 활용하는 방식의 알고리즘
• 답을 구하기 위해 계산을 반복해야 하는 종류의 문제를 최적 부분 구조라고 하는데
  이런 문제에서 효과적
• 주어진 문제를 부분 문제로 나누고 부분 값을 이용해 원래 문제의 답을 산출
• 분할정복과 차이점은
  1) 동적계획법은 부분 문제의 정답을 한 번만 사용 -> 이후에는 계산x 답 이용해서 속도 향상
  2) 중복이 가능한 경우 : 다이나믹
  중복이 불가능한 경우 : 분할 정복

2. 예시

2-1. 연산횟수로 비교해보는 동적 계획법의 필요성

f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

• 위 문제를 풀기 위해서는 아래와 같은 동적 계획법 사용 가능
  
• 연산 횟수 비교
  

2-2. 피보나치

• 피보나치 수열을 재귀함수의 형태로 풀게되면 5번째 피보나치 수열을 구하기 위해 15번의 함수 호출이 발생
  
• 동적계획법을 사용하면 반복 계산을 줄일 수 있음 (how ? 이전 계산 값은 배열에 저장)
• 대표적 방식은
  1) Top-down : 큰 문제에서부터 작은 문제로 분할

int memo[100]{}; 
//메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
  if (n<=1) //0번째, 1번째 피보나치 수
    return n;
  if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]; //메모 리턴
  memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
  return memo[n];
}

2) Bottom-up : 작은 문제에서 쌓아서 큰 문제를 푸는 것

int d[100];
int fibonacci(int n) {
  d[0] = 0;
  d[1] = 1;
  
  for(int i=2; i<=n; i++){
    d[i] = d[i-1] + d[i-2];
  }
  
  return d[n];
}

3. 문제풀이 전략

1. 점화식의 정의를 세운다.
2. 실제 점화식을 만든다.

4. 핵심정리

• dp의 부분 문제는 한 번만 풀어야 함
• 정답을 한 번 구했으면, 어딘가에 메모해놓기
• 메모하는 것을 코드에서는 배열로 구현할 수 있음
• 메모한다고 해서 Memoization 이라는 용어를 씀
• dp,다이나믹 프로그래밍, 동적 계획법의 이름 자체에는 큰 의미가 없음

참고자료 )

나무위키
자바스크립트로 알고리즘 정리하기 #9 다이나믹 프로그래밍 개념