Memoization

[메모이제이션 구현 패턴]

1. 항상 기저를 먼저 처리한다.
   • 다른 오류들을 피하기 위해 유용하다.
2. 함수의 반환 값이 0이라는 것을 이용해 cache[]를 모두 -1로 초기화 한다.
   • 만약 함수의 반환값이 -1이면 다른값으로 대체.
3. ret 가 cache[a][b]에 대한 참조형(reference)이다.
   • 참조형 이기 때문 값도 변하기 때문 답을 저장할 때도 편하다. cache가 다차원일때 유용하며 인덱스 순서등을 바꿀때 오류를 줄여준다.
4. memset()을 이용해 cache[] 초기화.
   • 메모이제이션에 배열을 초기화하는데 유요하다. 하지만 제한적임. 0,-1 로 초기화할떄만 쓰자.

// 전부 -1로 초기화
int cache[2500][2500];
// a와 b는 각각 [0,2500) 구간 안의 정수
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수,
int someObscureFunction(int a, int b){
  //기저사례를 처음에 처리한다.
  if(...) return ...;
  //(a,b)에 대한 답을 구한 적이 있으면 곧장 반환
  int &ret = cache[a][b];
  if(ret!= -1) return ret;
  // 여기서 답을 계산한다.
  ...
  return ret;
}
int main(){
  // cache 초기화
  memset(cache,-1,sizeof(cache));
}