동적계획법

분할정복과 비슷하다. 문제를 작게 나눈 뒤 조각의 답을 계산하고, 이 답들로 부터 원래의 문제에 대한 답을 구한다.

동적계획법은 이항계수를 통해 쉽게 알 수 있다.

int bino(int n, int r) {
    if(r==0 || n==r) return 1;
    return bino(n-1, r-1) + bino(n-1, r);
}

하지만, 이는 중복으로 호출되는 함수가 많다.

캐시 배열을 만들어 각 입력에 대한 반환값을 저장해놨다가 함수가 호출될 때마다 이 배열에 접근해 값이 저장되었는지를 확인한 후 저장되어있다면 즉시 반환한다.

메모이제이션 : 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

int cache[30][30] // -1로 초기화
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);
}

메모이제이션은 참조적 투명함수에만 적용된다. (입력이 같으면 출력값도 항상 같은 경우)

메모이제이션 구현 패턴

1. 입력 범위 벗어난 경우 처리

2. cache[] 를 항상 -1로 처리 ( 반환값이 항상 0이상이라는 가정하에 )

3. ret가 cache[]에 대한 참조형이다. ret를 바꾸면 cache[]도 바뀐다.

4. memset( cache, -1, sizeof(cache));를 사용한다.(주의)

int cache[2500][2500]; // -1로 초기화
​
int someObscureFunction(int a, int b) {
    if( ... ) return ...;
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    ... // 여기에서 답계산
    return ret;
}
​
int main() {
    memset(cache, -1, sizeof(cache));
}