<종만북> 08. 동적계획법_외발 뛰기 (Jumpgame)

밑에 그림처럼 n x n 크기의 격자에 1부터 9까지 정수를 쓴 게임판이 있다. 이 게임의 목적은 게임판의 왼쪽 위 칸에서 시작해 게임파의 맨 오른쪽 아래 칸에 도착하는 것이다.
각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있다.

코드 8.4

int n, board[100][100];
bool jump(int y, int x) {
	if (y >= n || x >= n) return false;

	if (y == n - 1 && x == n - 1) return true;

	int jumpSize = board[y][x];
	return jump(y + jumpSize, x) || jump(y, x + jumpSize);
}

1. 기저사례: 게임 판을 벗어난 경우 false, 마지막 칸에 도달한 경우 true
2. 현재 칸에 있는 숫자=jumpSize 저장 후, 오른쪽으로 뛸 경우 jump(y, x+jumpSize), 아래쪽으로 뛸 경우 y+jumpSize, x) 중 true 인 값을 반환한다.
3. jump(),는 참조적 투명함수(입력이 고정되어 있을 때 그 결과가 항상 같은 함수) 이기 때문에 메모이제이션 적용이 가능하다.

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);
}