8. 동적계획법(DP) 2

메모이제이션 구현 패턴

int fun(int a, int b) {
    // Process the base case
    if (...) return ...;

    // (a, b)에 대한 답을 구한 적이 있으면 return
    int& ret = cache[a][b];
    if (ret != -1) return ret;

    // Get what you want here
    ...
    return ret;
}

memset(array, 0, sizeof(array));

for문보다 쉽게 초기화 할 수 있음. 단, 0과 -1만 '운 좋게도' 초기화 될 수 있습니다.

메모이제이션의 시간 복잡도 분석

= (부분 문제 수) x (한 부분 문제 당 반복문의 수행 횟수)