[Algorithm] 🦘片足で踊る

0、問題

奪い合いに飽きた河と泳勲は、奪い合いの変種ゲームをすることにした.このゲームは、図に示すように、n*nサイズのメッシュに1から9まで書き込む整数で始まります.毎回の人は一番左上の格子から始め、片足で右下の格子にジャンプしなければなりません.この場合、各セルの数値に従って右または下のセルに移動できますが、ゲームエリアから離れることはできません.
バランスを崩して、もう片方の足で立ったり転んだりしても負けてしまうが、河と泳勲は若くて活気に満ちているので、片方の足で走っても何でもない.しかし,与えられたゲームボードでは,起点から終点までの方法が存在しない可能性が懸念される.例えば、図(a)のゲームボードでは、矩形のセルを介して終点に到達することができるが、1つの数字が置換された図(b)では到達できない.
ゲーム開始時に左上隅の始点から右下隅の始点に到達するようにプログラムを作成します.
入力
入力された最初の行は、テストケースの数C(C<=50)を示します.各テストケースの最初の行では、グリッドのサイズがn(2<=n<=100)であり、n行の各n個の数字が左上から各セルに書き込まれます.右下隅の端点位置は0です.
しゅつりょく
各テストケースについて、「YES」(始点から終点まで)と「NO」(そうでない場合)を出力します.(引用符は含まれません)

1.問題の簡単な説明

各セルの数値を左右に移動または下に移動して、目的地に到達できるかどうかを決定します.

2.アイデア

注釈構築ちゅうしゃくこうぞう:保存して使用(重複演算を減らす)ほぞんしてしよう

3.コア解答

1)注記

if(cache[y][x] != -1)
			return cache[y][x];
		
int jumpSize = board[y][x];
		
return cache[y][x] = jump(y+jumpSize, x) | jump(y, x+jumpSize);

4.コード

import java.util.*;

public class DP_EX_1 {
	static int n;
	static int board[][] = new int[100][100];
	static int cache[][] = new int[100][100];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		while(tc > 0) {
			n = sc.nextInt();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					board[i][j] = sc.nextInt();
					cache[i][j] = -1;
				}
			}
			
			if(jump(0,0) == 1)
				System.out.println("YES");
			else
				System.out.println("NO");
			
			tc--;
		}
	}
	
	static int jump(int y, int x) {
		if(y>=n || x>=n) return 0;
		if(y == n-1 && x == n-1) return 1;
		
		if(cache[y][x] != -1)
			return cache[y][x];
		
		int jumpSize = board[y][x];
		
		return cache[y][x] = jump(y+jumpSize, x) | jump(y, x+jumpSize);
	}

}

5.結果

成功～