分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 龙与地下城游戏问题 * * 【题目】 * 给定一个二维数组map含义是一张地图例如如下矩阵 * -2 -3 3 * -5 -10 1 * 0 30 -5 * 游戏的规则如下: * 骑士从左上角出发每次只能向右或向下走最后到达右下角见到公主。 * 地图中每个位置的值代表骑士要遭遇的事情。如果是负数说明此处有怪兽要让骑士损失血量。如果是非负数代表此处有血瓶能 * 让骑士回血。 * 骑士从左上角到右下角的过程中走到任何一个位置时血量都不能少于1。 * 为了保证骑士能见到公主初始血量至少是多少根据map返回初始血量。 * * 【难度】 * 中等 * * 【解答】 * 如果map大小为MxN经典动态规划方法的时间复杂度为O(MxN)额外空间复杂度为O(MxN)。结合空间压缩之后可以将额外空间复杂 * 度降至O(min{M,N})。空间压缩的原理请参考“矩阵的最小路径和”问题这里不再详述。 * * 请参看如下代码中的minHP2方法。 * * author Created by LiveEveryDay */ public class DungeonsAndDragons2 { public static int minHP2(int[][] m) { if (m null || m.length 0 || m[0] null || m[0].length 0) { return 1; } int more Math.max(m.length, m[0].length); int less Math.min(m.length, m[0].length); boolean rowMore more m.length; int[] dp new int[less]; int tmp m[m.length - 1][m[0].length - 1]; dp[less - 1] tmp 0 ? 1 : -tmp 1; int row 0; int col 0; for (int j less - 2; j 0; j--) { row rowMore ? more - 1 : j; col rowMore ? j : more - 1; dp[j] Math.max(dp[j 1] - m[row][col], 1); } int chosen1 0; int chosen2 0; for (int i more - 2; i 0; i--) { row rowMore ? i : less - 1; col rowMore ? less - 1 : i; dp[less - 1] Math.max(dp[less - 1] - m[row][col], 1); for (int j less - 2; j 0; j--) { row rowMore ? i : j; col rowMore ? j : i; chosen1 Math.max(dp[j] - m[row][col], 1); chosen2 Math.max(dp[j 1] - m[row][col], 1); dp[j] Math.min(chosen1, chosen2); } } return dp[0]; } public static void main(String[] args) { int[][] m {{-2, -3, 3}, {-5, -10, 1}, {0, 30, -5}}; System.out.printf(The min HP is: %d, minHP2(m)); } } // ------ Output ------ /* The min HP is: 7 */
【中等】龙与地下城游戏问题－Java：经典动态规划结合空间压缩解法
分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 龙与地下城游戏问题 * * 【题目】 * 给定一个二维数组map含义是一张地图例如如下矩阵 * -2 -3 3 * -5 -10 1 * 0 30 -5 * 游戏的规则如下: * 骑士从左上角出发每次只能向右或向下走最后到达右下角见到公主。 * 地图中每个位置的值代表骑士要遭遇的事情。如果是负数说明此处有怪兽要让骑士损失血量。如果是非负数代表此处有血瓶能 * 让骑士回血。 * 骑士从左上角到右下角的过程中走到任何一个位置时血量都不能少于1。 * 为了保证骑士能见到公主初始血量至少是多少根据map返回初始血量。 * * 【难度】 * 中等 * * 【解答】 * 如果map大小为MxN经典动态规划方法的时间复杂度为O(MxN)额外空间复杂度为O(MxN)。结合空间压缩之后可以将额外空间复杂 * 度降至O(min{M,N})。空间压缩的原理请参考“矩阵的最小路径和”问题这里不再详述。 * * 请参看如下代码中的minHP2方法。 * * author Created by LiveEveryDay */ public class DungeonsAndDragons2 { public static int minHP2(int[][] m) { if (m null || m.length 0 || m[0] null || m[0].length 0) { return 1; } int more Math.max(m.length, m[0].length); int less Math.min(m.length, m[0].length); boolean rowMore more m.length; int[] dp new int[less]; int tmp m[m.length - 1][m[0].length - 1]; dp[less - 1] tmp 0 ? 1 : -tmp 1; int row 0; int col 0; for (int j less - 2; j 0; j--) { row rowMore ? more - 1 : j; col rowMore ? j : more - 1; dp[j] Math.max(dp[j 1] - m[row][col], 1); } int chosen1 0; int chosen2 0; for (int i more - 2; i 0; i--) { row rowMore ? i : less - 1; col rowMore ? less - 1 : i; dp[less - 1] Math.max(dp[less - 1] - m[row][col], 1); for (int j less - 2; j 0; j--) { row rowMore ? i : j; col rowMore ? j : i; chosen1 Math.max(dp[j] - m[row][col], 1); chosen2 Math.max(dp[j 1] - m[row][col], 1); dp[j] Math.min(chosen1, chosen2); } } return dp[0]; } public static void main(String[] args) { int[][] m {{-2, -3, 3}, {-5, -10, 1}, {0, 30, -5}}; System.out.printf(The min HP is: %d, minHP2(m)); } } // ------ Output ------ /* The min HP is: 7 */
