알고리즘 - 메모이제이션 코드 패턴과 외발뛰기 문제

// 전부 -1로 초기화
int cache[2500][2500];

// a, b 는 구간 안의 정수를 말하고, 반환 값은 항상 int형인 음이 아닌 정수
int Function(int a, int b){
    //[1] 맨 처음에는 기저 사례 처리하기
    if(...) return ...;
    
    //[2] (a, b)에 대한 답을 구한 적이 있다면 그것을 캐시에서 바로 반환
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    
    //[3] 없었을 경우 답을 계산하여 넣기
    ...
    return ret;
}

memset(cache, -1, sizeof(cache));

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
typedef long long ll;

using namespace std;

int board[101][101];
int cache[101][101];
int n;

// 마지막 칸에 도달할 수 있는지 여부를 반환하는 함수
int move(int y, int x) {
	// 1. 무조건 기저사례 먼저 처리
	// 범위를 넘어갔을 경우
	if (x >= n || y >= n) return 0;
	// 도착했을 경우
	if (x == n - 1 && y == n - 1) return 1;

	// 2. 이미 캐시배열에 계산된 값이 있었을 경우 그것을 반환
	int& ret = cache[y][x];
	if (ret != -1) return ret;

	// 3. 아닐 경우 계산하여 값 저장
	// 칸의 이동 거리를 저장한다.
	int movingSize = board[y][x];

	// 아래로 혹은 오른쪽으로 이동시켜 본다.
	// 도달할 수 없었을 경우는 cache[y][x]에 0이, 도착했을 경우 1이 저장된다.
	return ret = (move(y + movingSize, x) || move(y, x + movingSize));
}


int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;
		// 캐시배열 초기화
		memset(cache, -1, sizeof(cache));
		
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				cin >> board[j][k];
			}
		}

		int result = move(0, 0);
		if (result == 1) cout << "YES\n";
		else cout << "NO\n";

		memset(cache, -1, sizeof(cache));
	}
	
	return 0;
}