自主设计和创建网站,建设云购网站,新网域名管理,个人网站服务器题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻…题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出7 解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。 示例 2
输入dungeon [[0]] 输出1 提示
m dungeon.length n dungeon[i].length 1 m, n 200 -1000 dungeon[i][j] 1000
思路
问题描述地下城由一个m x n的网格组成骑士从左上角出发必须通过对抗恶魔来拯救公主目标是找到骑士进入地下城所需的最低初始健康点数。
解题思路 这是一个动态规划问题。我们可以从右下角开始逆向考虑定义 dp[i][j] 为从位置 (i, j) 到达右下角时所需的最低初始健康点数。为了逆向推导我们从右下角开始向左上角遍历。
对于最后一行和最后一列只能往右或往下移动因此需要考虑从当前位置 (i, j) 出发的下一个位置 (i1, j) 或 (i, j1)并且需要保证 dp[i][j] 大于等于1。对于其他位置我们需要考虑向右或向下移动并且选择路径中的最小初始健康点数。因此dp[i][j] 取决于 (i1, j) 和 (i, j1) 中的较小值且需要保证 dp[i][j] 大于等于1。
最终初始健康点数应该大于等于 dp[0][0]。
代码
object Solution {def calculateMinimumHP(dungeon: Array[Array[Int]]): Int {val m dungeon.lengthval n dungeon(0).lengthval dp Array.ofDim[Int](m, n)dp(m - 1)(n - 1) math.max(1, 1 - dungeon(m - 1)(n - 1))for (i - m - 2 to 0 by -1) {dp(i)(n - 1) math.max(1, dp(i 1)(n - 1) - dungeon(i)(n - 1))}for (j - n - 2 to 0 by -1) {dp(m - 1)(j) math.max(1, dp(m - 1)(j 1) - dungeon(m - 1)(j))}for (i - m - 2 to 0 by -1) {for (j - n - 2 to 0 by -1) {dp(i)(j) math.max(1, math.min(dp(i 1)(j), dp(i)(j 1)) - dungeon(i)(j))}}dp(0)(0)}def main(args: Array[String]): Unit {val dungeon1 Array(Array(-2, -3, 3), Array(-5, -10, 1), Array(10, 30, -5))println(calculateMinimumHP(dungeon1)) // 输出 7val dungeon2 Array(Array(0))println(calculateMinimumHP(dungeon2)) // 输出 1}
}
