[DP] 메모이제이션 구현 레시피

1. 기저 사례를 가장 먼저 처리. 입력 범위 벗어난 경우(nx < 0 && nx > N 등) 포함

 

2. cache[]를 전부 -1로 초기화.

 

3. ret는 cache[a][b]의 참조 변수. 즉 ret의 값이 바뀌면, cache[a][b]의 값도 바뀜.

 

4. memset()을 이용해 cache를 초기화. 하지만, 굉장히 제한적인 경우에만 쓸것!

 

 

 

 

---

 

 

레시피의 예.

#include <memory.h> // memset을 쓰기 위해 include(백준 등에서 쓰기 위함).

int cache[2500][2500]; // 2. 전부 -1로 초기화 해둔다.

int dpFunction(int a, int b)
{
	if (...) return ...; // 1. 기저 사례를 가장 먼저 처리.
    
	int& ret = cache[a][b]; // 3. ret는 cache[a][b]의 참조 변수.
	if (ret != -1) return ret; // 답을 구한 적 있으면 바로 리턴.
    
	...
    
	return ret;
}


int main(void)
{
	memset(cache, -1, sizeof(cache)); // 4. memset으로 cache를 -1로 초기화.
}