定西兰州网站建设,网站投资设计,广州站是不是广州火车站,餐饮logo创意设计大家好#xff0c;我是晴天学长#xff0c;非常经典实用的记忆化搜索题#xff0c;当然也可以用dp做#xff0c;我也会发dp的题解#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .迷宫逃脱 迷官逃脱…大家好我是晴天学长非常经典实用的记忆化搜索题当然也可以用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% 试题链接
