当前位置：首页 > 牛客 > 牛客网第51817题解题报告：动态规划求解地牢游戏最小血量问题

牛客网第51817题解题报告：动态规划求解地牢游戏最小血量问题

3个月前 (07-22)

一、题目解读

牛客网第51817题要求玩家在地牢游戏中计算从起点到终点所需的最小初始血量。地牢由二维数组表示，每个元素为负数或正数，分别代表扣血或回血。玩家需确保到达终点时血量≥1，求初始最小血量。问题本质是路径规划与资源优化，需考虑路径上的血量动态变化。

二、解题思路

作者采用动态规划（Dynamic Programming）的逆向求解策略：

1. 核心思想：从终点反向推导，计算每个位置所需的最小初始血量。

2. 状态定义：dp[i][j]表示从位置(i,j)到达终点所需的最小初始血量。

3. 状态转移方程：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])，即从下方或右方相邻位置的最小需求血量减去当前格子扣血值，并确保血量≥1。

4. 边界条件：终点位置dp[n-1][m-1]为max(1, 1 - dungeon[n-1][m-1])，最后一行与最后一列需逆向初始化。

三、解题步骤

1. 输入与初始化：读取地牢矩阵大小n×m，构建dp数组。

2. 终点初始化：dp[n-1][m-1]根据终点扣血值计算最小血量。

3. 边界填充：逆向计算最后一行与最后一列的血量需求，确保每个位置血量合法。

4. 动态规划填充：从右下角向左上角遍历，利用状态转移方程更新dp[i][j]。

5. 输出结果：返回dp[0][0]即起点所需最小初始血量。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计算最小初始血量
int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int n = dungeon.size(); // 地牢行数
    if (n == 0) return 1;   // 边界处理：空地牢返回1
    int m = dungeon[0].size(); // 地牢列数

    // dp[i][j]：从(i,j)到终点所需的最小初始血量
    vector<vector<int>> dp(n, vector<int>(m, 0));
    
    // 1. 终点初始化
    dp[n-1][m-1] = max(1, 1 - dungeon[n-1][m-1]); // 终点血量需≥1，扣血后调整

    // 2. 逆向填充最后一行
    for (int j = m-2; j >= 0; --j) {
        dp[n-1][j] = max(1, dp[n-1][j+1] - dungeon[n-1][j]); // 从右向左推导
    }
    
    // 3. 逆向填充最后一列
    for (int i = n-2; i >= 0; --i) {
        dp[i][m-1] = max(1, dp[i+1][m-1] - dungeon[i][m-1]); // 从下向上推导
    }
    
    // 4. 动态规划填充其余位置
    for (int i = n-2; i >= 0; --i) {
        for (int j = m-2; j >= 0; --j) {
            int min_required = min(dp[i+1][j], dp[i][j+1]); // 取下方/右方较小需求
            dp[i][j] = max(1, min_required - dungeon[i][j]); // 扣当前格子血量并确保≥1
        }
    }
    
    return dp[0][0]; // 返回起点所需最小血量
}

int main() {
    ios::sync_with_stdio(false); // 加快输入输出
    cin.tie(nullptr);
    
    int n, m; // 输入地牢尺寸
    cin >> n >> m;
    vector<vector<int>> dungeon(n, vector<int>(m)); // 构建地牢矩阵
    
    // 输入地牢元素
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> dungeon[i][j];
        }
    }
    
    cout << calculateMinimumHP(dungeon) << endl; // 输出结果
    return 0;
}