[알고리즘 문제해결전략] 동적 계획법 예시 jump

가장 기본적인 형태 중 하나이다. 

 

1. 주어진 문제를 완전 탐색을 이용해 해결한다. 

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다. 

 

int n, board[100][100];
int cache[100][100];
int jump2(int y, int x) {
    if (y >= n || x >= n) return 0; //기저사례 처리
    if (y == n - 1 && x == n - 1) return 1; //끝에 도달 
    //메모이제이션
    int& ret = cache[y][x];
    //이미 계산된 값이라면 그 값을 반환
    if (ret != -1) return ret;
    int jumpsize = board[y][x];
    return ret = (jump2(y + jumpsize, x) || jump2(y, x + jumpsize));
}