174. 地下城游戏

[linqibin]

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

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

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

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

说明:

骑士的健康点数没有上限。

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

思路：第一反应是用递归暴力枚举所以路线，找出最小值。结果遇到一个很大迷宫爆栈了。想了很久没能做出来。看了评论才知道怎么做。
新知识点GET，动态规划
当问题符合两个条件时，就可以使用动态规划求解：

1. 无后效性。即如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这个阶段以前各状态的影响。
2. 最优子结构。即一个问题的最优解能由小问题的最优解推出。

要找个时间认真看一下动态规划，再做相关的题

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
function calculateMinimumHP(dungeon) {
    const row = dungeon.length;
    const column = dungeon[0].length;
    const max = Math.max;
    const min = Math.min;
    
    for (let i = row - 1; i >= 0; --i) {
        for (let j = column - 1; j >= 0; --j) {
            if (i === row - 1 && j === column - 1)
                // 到最后所需的生命值
                dungeon[i][j] = max(- dungeon[i][j], 0);
            else if (i === row - 1 && j !== column - 1)
                // 最右一列所需的生命值只取决于其下方的格子
                dungeon[i][j] = max(dungeon[i][j + 1] - dungeon[i][j], 0);
            else if (i !== row - 1 && j === column - 1)
                // 最下一行所需的生命值只取决于其右方的格子
                dungeon[i][j] = max(dungeon[i + 1][j] - dungeon[i][j], 0);
            else
                // 其格子所需的生命值取决于右边和下边的格子
                dungeon[i][j] = max(min(dungeon[i + 1][j], dungeon[i][j + 1]) - dungeon[i][j], 0);
        }
    }
    
    return dungeon[0][0] + 1;
}