大家好，我是晴天學長，非常經典實用的記憶化搜索題，當然也可以用dp做，我也會發dp的題解，需要的小伙伴可以關注支持一下哦！后續會繼續更新的。💪💪💪

---

1) .迷宮逃脫

迷官逃脫[算法賽]
問題描述
在數學王國中，存在- -個大小為N x M的神秘迷言。第i行第j個位置坐標為(i,j),每個位置(i;,j) (1≤i≤N,1≤j≤M)都對應著一個正整數Aij。迷宮的左上角坐標為(1,1)， 右下角坐標為(N,M)。
小藍初始位于坐標(1,1),并攜帶著Q把密匙。他的目標是移動到迷言的終點，即坐標(N, M)處。但是通往迷宮盡頭的道路并不是一-帆風順的， 在前進的過程中，他遇到了一些奇特的規則。

規則如下:

1.小藍每次只能向右移動一個位置或向下移動一個位置。
2.當小藍所在位置的數和下一步移動位置的數互質時，會有一扇封閉的鐵門， 小藍需要消耗-把密匙來打開鐵門，打開鐵門后，這把鑰匙將被摧毀。如果沒有密匙，小藍將無法移動到該位置。
你需要輸出小藍從起點到終點路徑之和的最大值，如果無法從起點到達終點，輸出-1。

輸入格式

第一行輸入包含3個整數N, M, Q,分別為迷言的大小和密匙的數量。
接下來輸入N行，每行M個整數,為迷言上的數值。

輸出格式

輸出僅一-行，包含-個整數，表示管案。
樣例輸入

331
139
樣例輸出

28

---

2) .算法思路

逃脫迷宮（記憶化搜索）
1.使用快讀接受數據，矩陣大小從11開始，以及使用快輸。

2.從重點開始
1.出邊界或者要是為-1，就返回最小值
2.到達終點，返回矩陣。
3.記憶化中有就直接返回。
4.當前位置
可以走上面，也可以走下面，取最大值。
存在記憶化的矩陣中。
5.返回結果。

---

3）.算法步驟

1.從第一行讀取輸入值 N、M 和 Q。
2.創建一個名為 “grid” 的二維數組，維度為 [1100][1100]。
3.讀取 N 行輸入，并使用這些值填充 grid 數組。
4.將變量 “ans” 初始化為 0。
5.使用參數 N、M、Q 和 grid 調用 dfs() 方法來計算最大和。
6.如果 “ans” 大于 0，則打印其值；否則，打印 -1。
7.刷新輸出流。

dfs() 方法執行實際的動態規劃計算。它以當前位置 (i, j)、剩余步數 (Q) 和網格作為輸入。它使用記憶化技術來存儲先前計算過的值，以避免重復計算。
dfs() 方法的步驟如下：

1）檢查基本情況：如果 i 或 j 等于 0，或者 Q 等于 -1，則返回 Long.MIN_VALUE。
2）檢查當前位置是否為目標位置（即 i = 1 且 j = 1）。如果是，則返回該位置的 grid 值。
3）檢查當前位置和剩余步數的結果是否已經被記憶化。如果是，則返回記憶化的結果。
4）根據當前值和左側值是否互質（最大公約數為 1）來計算 “floor” 值。
5）根據當前值和上方值是否互質來計算 “left” 值。
6）計算結果為當前值與兩個遞歸調用的最大值之和：向左移動（j 減 1）和向上移動（i 減 1）。
7）將結果進行記憶化。
8）返回結果。

gcd() 方法是一個輔助函數，使用歐幾里德算法計算兩個數的最大公約數。

---

4）. 代碼實例

import java.io.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static String[] lines;static long[][][] memo = new long[1100][1100][4];static long ans = 0;public static void main(String[] args) throws IOException {lines = in.readLine().split(" ");int N = Integer.parseInt(lines[0]);int M = Integer.parseInt(lines[1]);int Q = Integer.parseInt(lines[2]);long[][] grid = new long[1100][1100];//接受數據for (int i = 1; i <= N; i++) {lines = in.readLine().split(" ");for (int j = 1; j <= M; j++) {grid[i][j] = Integer.parseInt(lines[j - 1]);}}// 開始ans = dfs(N, M, Q, grid);out.println(ans <= 0 ? -1 : ans);out.flush();}private static long dfs(int i, int j, int Q, long[][] grid) {if (i == 0 || j == 0 || Q == -1) return Long.MIN_VALUE;if (i == 1 && j == 1) return grid[i][j];//緩存的值if (memo[i][j][Q]!=0) return memo[i][j][Q];//從上面走,先判斷是否互質int floor = gcd((int) grid[i][j], (int) grid[i][j - 1]) == 1 ? 1 : 0;//從左面走int left = gcd((int) grid[i][j], (int) grid[i - 1][j]) == 1 ? 1 : 0;//取最大long result = grid[i][j] + Math.max(dfs(i, j - 1, Q - floor, grid), dfs(i - 1, j, Q - left, grid));memo[i][j][Q] = result;return result;}//求是否互質private static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}

---

4）.總結

• 以后建議都用快讀快輸，不用只過60%，而且這兩個還要一起用，只用快讀只過95%！！

---

試題鏈接：