題目鏈接

leetcode在線oj題——地下城游戲

題目描述

惡魔們抓住了公主并將她關(guān)在了地下城 dungeon 的 右下角 。地下城是由 m x n 個(gè)房間組成的二維網(wǎng)格。我們英勇的騎士最初被安置在 左上角 的房間里，他必須穿過地下城并通過對(duì)抗惡魔來拯救公主。

騎士的初始健康點(diǎn)數(shù)為一個(gè)正整數(shù)。如果他的健康點(diǎn)數(shù)在某一時(shí)刻降至 0 或以下，他會(huì)立即死亡。

有些房間由惡魔守衛(wèi)，因此騎士在進(jìn)入這些房間時(shí)會(huì)失去健康點(diǎn)數(shù)（若房間里的值為負(fù)整數(shù)，則表示騎士將損失健康點(diǎn)數(shù)）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點(diǎn)數(shù)的魔法球（若房間里的值為正整數(shù)，則表示騎士將增加健康點(diǎn)數(shù)）。

為了盡快解救公主，騎士決定每次只 向右 或 向下 移動(dòng)一步。

返回確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。

注意：任何房間都可能對(duì)騎士的健康點(diǎn)數(shù)造成威脅，也可能增加騎士的健康點(diǎn)數(shù)，包括騎士進(jìn)入的左上角房間以及公主被監(jiān)禁的右下角房間。

題目示例

示例1

輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
輸出：7
解釋：如果騎士遵循最佳路徑：右 -> 右 -> 下 -> 下 ，則騎士的初始健康點(diǎn)數(shù)至少為 7 。

示例2

輸入：dungeon = [[0]]
輸出：1

題目提示

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

解題思路

之前介紹的動(dòng)態(tài)規(guī)劃題目都是從左上角開始，迭代動(dòng)態(tài)規(guī)劃方程，一直走到右下角，得到最終的結(jié)果，但是這道題是需要我們給出初始的血量，因此需要從右下角開始，向左上角迭代

當(dāng)進(jìn)入到負(fù)數(shù)的房間時(shí)，騎士會(huì)扣血，但是我們是從最后一個(gè)房間推導(dǎo)前面的房間，因此往前走遇到負(fù)數(shù)需要加血，遇到正數(shù)可以減血

而當(dāng)前狀態(tài)最小血量應(yīng)該是走下面和走右面都可以支撐，因此是求下面和右面狀態(tài)的較小者 - 當(dāng)前房間的buff

dp[i][j] = min(dp[i + 1][j], dp[i + 1][j]) - dungeon[i][j];

如果得到的數(shù)字是負(fù)數(shù)，說明到這個(gè)位置騎士已經(jīng)死了，這是不應(yīng)該的，騎士最小也要有一點(diǎn)血，因此將其重新變?yōu)?點(diǎn)血

dp[i][j] = Math.max(1, dp[i][j]);

從右下角開始迭代需要考慮越界問題，最下面一行和最右面一列會(huì)出現(xiàn)越界，為了簡(jiǎn)化代碼，可以將dp數(shù)組多添加一行一列，而為了不改變動(dòng)態(tài)方程的有效性，最下面一行和最右面一列需要填入不影響其他位置的值——正無窮大

而為了使得最后一個(gè)房間的buff減益后還能剩一點(diǎn)血量，dp[m - 1][n] = dp[m][n - 1] = 1;文章來源地址http://www.zghlxwxcb.cn/news/detail-513776.html

完整代碼

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 0; i <= n; i++){
            dp[m][i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = 1;
        dp[m][n - 1] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
}

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——地下城游戲的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！