走迷宫问题

问题描述

骑士要从房间左上角走到右下角，每次只能向右或向下走一步。 房间里的数字表示骑士生命值的变化值，骑士血量归零就会死亡，至少要有 1 点 HP。 骑士为了救到公主，至少需要多少点生命值？ 上图所需最少HP为7。

分析

这个题的关键在于：不仅要求路程和，还要确保路上的每个点HP都大于0。
他的小规模的问题是从右下角开始的，而不是左上角。具有最优子结构。

dp[i][j]表示从这个格子到达终点至少需要的血量，转移方程为：

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size();
    int n = dungeon[0].size();
    // 初始化最后一行
    dungeon[m - 1][n - 1] = max(1 - dungeon[m - 1][n - 1], 1);
    for (int j = n - 2; j >= 0; --j)
        dungeon[m - 1][j] = max(dungeon[m - 1][j + 1] - dungeon[m - 1][j], 1);
    // 初始化最后一列
    for (int i = m - 2; i >= 0; --i)
        dungeon[i][n - 1] = max(dungeon[i + 1][n - 1] - dungeon[i][n - 1], 1);
    // 其他行列
    for (int i = m - 2; i >= 0; --i)
        for (int j = n - 2; j >= 0; --j)
            dungeon[i][j] = min(
                max(dungeon[i + 1][j] - dungeon[i][j], 1),
                max(dungeon[i][j + 1] - dungeon[i][j], 1));
    return dungeon[0][0];
}