(작성중)Dynamic Programming

동적 프로그래밍(X) 동적 계획법(O)

동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있다. 이렇게 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 한다.

동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항 계수(binomial co-efficient)의 계산이다. 이항계수는 n개의 서로 다른 원 소 중에서 r개의 원소를 순서없이 골라내는 방법의 수를 나타내는 것으로, 이항 계수에는 다음과 같은 점화식이 성립한다.

nCr = n-1Cr-1 + n-1Cr

public int bino(int n, int r){
  // 기저 사례: n=r(모든 원소를 다 고르는 경우) 혹은 r=0 (고를 원소가 없는 경우)
  if(r == 0 || n == r) return 1;
  return bino(n-1, r-1) + bino(n-1, r);

}

완전탐색

int cache[30][30];
public int bino(int n, int r){
  // 기저 사례: n=r(모든 원소를 다 고르는 경우) 혹은 r=0 (고를 원소가 없는 경우)
  if(r == 0 || n == r) return 1;

  if(cache[n][r] != -1){
    return cache[n][r];
  }

  return cache[n][r] = bino(n-1, r-1) + bino(n-1, r);

}

DP

함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성(referential transparency)이라고 한다. 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다.