大家好，我是晴天學長，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) .算法思路
迷宮逃脫（DP版）
1.用快讀快輸接收數據。
2.建立矩陣
3.打表，建立一個三維的dp表。
4.狀態轉移方程
1.從上面來
int floor=
2.從左面來
int right=
3.狀態轉移方程
dp[i][j][k] = Math.,max();
4.輸出dp[n][m][k]（帶循環）。
3）.算法步驟
1.讀取輸入的N、M和Q的值（迷宮的尺寸和最大鑰匙數量）。
2.創建一個名為"grid"的二維網格數組，用于存儲迷宮中每個單元格的值。
3.初始化動態規劃數組"dp"，其維度為[1100][1100][4]，用于存儲不同鑰匙數量下每個位置的最大分數。
4.讀取迷宮中每個單元格的值，并將其存儲在"grid"數組中。
5.在"dp"數組中設置起始位置（1, 1）的初始值。因為它是起始位置，所以分數等于該單元格的值。
6.開始動態規劃過程，遍歷迷宮中的每個單元格。
- 對于每個單元格，遍歷鑰匙數量（從0到Q），計算在給定鑰匙數量下到達該單元格的最大分數。
- 檢查是否可以從上方的單元格移動到當前單元格（即(i-1, j)）或從左側的單元格移動到當前單元格（即(i, j-1)）。
- 如果可以從上方單元格移動，根據上方單元格的分數和當前單元格的值更新當前單元格的最大分數。
- 如果可以從左側單元格移動，根據左側單元格的分數和當前單元格的值更新當前單元格的最大分數。
- 重復步驟6到步驟10，遍歷迷宮中的所有單元格。
7.找到最后一行和最后一列的單元格中不同鑰匙數量下的最大分數。
8.將最大分數作為結果進行打印輸出。如果最大分數小于或等于0，則輸出-1。
9.刷新輸出。
4）. 代碼實例
package LanQiaoTest.動態規劃;import jdk.swing.interop.SwingInterOpUtils;import java.io.*;public class 迷宮逃脫_DP {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static long dp[][][] = new long[1100][1100][4];static String[] lines;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[N + 10][M + 10];// 接收數據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]);}}//起點賦初值（因為起點沒有上一個的狀態，自己就是自己）for (int i = 0; i <= Q; i++) {dp[1][1][i] = grid[1][1];}//開始打表for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) {for (int k = 0; k <= Q; k++) {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;//注意鑰匙不能超了//上面來//是質數，必須有鑰匙。if (k - floor >= 0 && dp[i][j - 1][k - floor] != 0) {dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j - 1][k - floor] + grid[i][j]);}//左面來，注意更新最大值if (k - left >= 0 && dp[i - 1][j][k - left] != 0) {dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k - left] + grid[i][j]);}}}}//找到終點的最大值long result = 0;for (int i = 0; i <= Q; i++) {result = Math.max(result, dp[N][M][i]);}out.println(result <= 0 ? -1 : result);out.flush();}private static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}4）.總結
- 越界的地方不能算進去，不然不可達到的地方也會加入答案中。
試題鏈接：
)
