동적 계획법은 분할 정복과 유사하지만, 이미 계산한 값을 중복해서 계산하지 않기 위해 따로 저장하는 메모이제이션 기법을 사용했다는 것이 주요 특징이다.
이 기법은 참조적 투명성을 가지고 있는 함수에 대해서 적용된다. 같은 입력이 들어왔을 때 항상 같은 출력을 반환한다는 것이다.
유의사항
(1) 입력이 정해진 범위를 벗어난 경우 등을 기저 사례로 처리하여 cache에 저장하기
(2) cache의 초기값을 -1과 같은 수로 두고 -1이 아니라면 이미 계산된 값이라 생각한다.
(3) 저장된 값을 반환하여 담는 ret변수는 &를 사용해서 “별칭”으로 선언한다. 이는 cache의 값을 그대로 가져오기 때문에, ret의 값을 바꾸면 cache의 값도 바뀌게 된다.
메모이제이션 기법을 이용해 nCr을 계산하는 함수
#include <iostream>
int cache[30][30];
int bino2(int n, int r) {
if (r == 0 || n == r)
return 1;
if (cache[n][r] != -1)
return cache[n][r];
return cache[n][r] = bino2(n - 1, r - 1) + bino2(n - 1, r);
}
시간 복잡도 계산
(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)