首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >地下城中的骑士:最低健康点数问题 Swift 解决方案

地下城中的骑士:最低健康点数问题 Swift 解决方案

原创
作者头像
Swift社区
发布于 2025-01-23 19:31:49
发布于 2025-01-23 19:31:49
4710
举报
文章被收录于专栏:Swift社区Swift社区

摘要

本文探讨了如何计算骑士在解救被困地下城公主时所需的最低初始健康点数。通过动态规划,我们实现了一个高效的解决方案,并在 Swift 中提供了可运行的代码示例,适合用于理解和实践。

问题描述

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意: 任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1:

代码语言:txt
复制
输入: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出: 7
解释: 如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。

示例 2:

代码语言:txt
复制
输入: dungeon = [[0]]
输出: 1

提示:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

Swift 题解答案

本题的核心是利用动态规划从目标位置向起始位置反推所需的最低健康点数。

代码解决方案

代码语言:swift
复制
func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
    let m = dungeon.count
    let n = dungeon[0].count

    // 初始化 dp 数组
    var dp = Array(repeating: Array(repeating: Int.max, count: n + 1), count: m + 1)
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1

    // 从右下角开始填表
    for i in stride(from: m - 1, through: 0, by: -1) {
        for j in stride(from: n - 1, through: 0, by: -1) {
            let minHealth = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(1, minHealth)
        }
    }

    return dp[0][0]
}

// 示例测试
let dungeon1 = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
print("最低初始健康点数:\(calculateMinimumHP(dungeon1))") // 输出: 7

let dungeon2 = [[0]]
print("最低初始健康点数:\(calculateMinimumHP(dungeon2))") // 输出: 1

代码分析

  1. 动态规划数组初始化
    • 我们创建了一个 dp 数组,其大小为 (m+1) x (n+1),并初始化为 Int.max。
    • 为方便计算,将 dp[m][n-1] 和 dp[m-1][n] 初始化为 1,代表救出公主后至少需要的健康点数。
  2. 从右下角向左上角反推
    • 对于每个房间,计算进入该房间后所需的最低健康点数。
    • 动态规划公式为:dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
  3. 返回结果
    • 起点 dp[0][0] 即为骑士所需的最低初始健康点数。

示例测试及结果

输入

输出

[-2, -3, 3, -5, -10, 1, 10, 30, -5]

7

[0]

1

[1, -2, 3, -4, 5, -6, 7, -8, 9]

6

时间复杂度

  • 动态规划填表:每个房间访问一次,时间复杂度为 O(m * n)。
  • 总体复杂度:O(m * n)。

空间复杂度

  • 动态规划数组:使用了大小为 (m+1) x (n+1) 的数组,空间复杂度为 O(m * n)。

总结

通过动态规划解决骑士地下城问题,可以高效计算骑士所需的最低初始健康点数。Swift 的实现清晰直观,适合学习和实际应用。在实际问题中,这种反向动态规划的思想还可推广到其他路径优化问题。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

目录
  • 摘要
  • 问题描述
  • Swift 题解答案
    • 代码解决方案
    • 代码分析
    • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档