动态规划实战：牛客51817题地下城游戏的最优解法详解

3天前牛客题解61

一、问题分析与解法思路

地下城游戏问题是一个典型的动态规划应用场景。我们需要逆向思考，从终点反推每个位置所需的最小初始生命值。这种方法可以避免正向思考时复杂的生命值跟踪问题。

二、完整代码实现（带详细注释）

#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));
    
    // 初始化终点位置
    dp[n-1][m-1] = max(1, 1 - dungeon[n-1][m-1]);
    
    // 初始化最后一行（只能向右移动）
    for (int j = m-2; j >= 0; --j) {
        dp[n-1][j] = max(1, dp[n-1][j+1] - dungeon[n-1][j]);
    }
    
    // 初始化最后一列（只能向下移动）
    for (int i = n-2; i >= 0; --i) {
        dp[i][m-1] = max(1, dp[i+1][m-1] - dungeon[i][m-1]);
    }
    
    // 动态规划填充其他位置（可以向右或向下移动）
    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);  // 禁用C与C++的输入输出同步
    cin.tie(nullptr);            // 解除cin与cout的绑定
    
    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;
}