DP(Dynamic Programming)패턴 연구

동적 계획법(dp)는 가장 흔한 문제 유형 중 하나이고 메모이제이션은 굉장히 자주 구현하게 된다. 

따라서 한 가지 패턴을 정해두고 풀게 되면 확실한 풀이 방법을 알 수 있을 것 같다. 

1. 가장 먼저 basecase 처리

2. cache[]를 모두 -1로 초기화하고, -1이 아니면 cache[]의 값이 없는 것으로 간주.

3. ret(리턴 값)을 참조형(reference)으로 관리하여 실수를 줄임

4. memset을 이용한 초기화

int cache[2500][2500];
 
int dp(int a, int b){
    // 1. base case 처리
    if(...) return ...;
    // (a, b)에 대한 답을 구한 적이 있으면 바로 반환
    int & ret = cache[a][b];  // 3. 참조형(int &)을 이용하여 ret 관리
    if(ret != -1) return ret; // 2. -1이 아니면 값이 없는 것으로 간주하여 리턴
    // 답 계산
    ...
    return ret;
}
 
int main(){
    // 4. memset으로 초기화
    memset(cache, -1, sizeof(cache)); 
}