174. 地下城游戏

题意：

解题思路：

1. 初始化公主节点的右侧跟下侧为1，这样就可以倒推算出到公主节点需要多少健康点数；
2. dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][i]);
3. dp[i][j]表示到(i, j)点需要最少的血量；
4. 方便计算多添加一行一列。使dp[n][m - 1] = 1, dp[m][m - 1] = 1;

PHP代码实现：

class Solution {
    /**
     * @param Integer[][] $dungeon
     * @return Integer
     */
    function calculateMinimumHP($dungeon) {
        $m = count($dungeon);
        $n = count($dungeon[0]);
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, PHP_INT_MAX));
        $dp[$m - 1][$n] = 1;
        $dp[$m][$n - 1] = 1;
        for ($i = $m - 1; $i >= 0; $i--) {
            for ($j = $n - 1; $j >= 0; $j --) {
                //选最小的值作为要走的路
                $minHp = min($dp[$i + 1][$j], $dp[$i][$j + 1]) - $dungeon[$i][$j];
                if ($minHp < 1) {
                    $dp[$i][$j] = 1;
                } else {
                    $dp[$i][$j] = $minHp;
                }
            }
        }
        return $dp[0][0];
    }
}

go代码实现：

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    dp := make([][]int, m + 1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n + 1)
    }
    for i := 0; i <= m; i++ {
        dp[i][n] = 1 << 31
    }
    for j := 0; j <= n; j++ {
        dp[m][j] = 1 << 31
    }
    // 设置起点默认值。因为dp[m-1][n-1] = 1 - dungeon[m-1][n-1],可以反推到公主节点
    dp[m][n - 1], dp[m - 1][n - 1] = 1, 1
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            minHp := min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
            if minHp < 1 {
                dp[i][j] = 1
            } else {
                dp[i][j] = minHp
            }
        }
    }
    return dp[0][0]
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}