【中等】龙与地下城游戏问题－Java：经典动态规划结合空间压缩解法

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package 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 */