大家好,我是晴天学长,非常经典实用的记忆化搜索题,当然也可以用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%!!
试题链接: