1. 題目解析

題目鏈接：174. 地下城游戲

這個(gè)問(wèn)題的理解其實(shí)相當(dāng)簡(jiǎn)單，只需看一下示例，基本就能明白其含義了。

2.算法原理

一、狀態(tài)表定義

在解決地下城游戲問(wèn)題時(shí)，我們首先需要對(duì)狀態(tài)進(jìn)行恰當(dāng)?shù)亩x。一個(gè)直觀的想法是，從起點(diǎn)開(kāi)始，到達(dá)[i, j]位置時(shí)所需的最低初始健康點(diǎn)數(shù)。然而，這樣的定義會(huì)導(dǎo)致?tīng)顟B(tài)轉(zhuǎn)移時(shí)面臨困難，因?yàn)楫?dāng)前位置的健康點(diǎn)數(shù)會(huì)受到后續(xù)路徑的影響。

為了解決這個(gè)問(wèn)題，我們采用另一種狀態(tài)定義方式：從[i, j]位置出發(fā)，到達(dá)終點(diǎn)時(shí)所需的最低初始健康點(diǎn)數(shù)。這樣定義的好處在于，當(dāng)我們?cè)赱i, j]位置時(shí)，后續(xù)的最佳狀態(tài)已經(jīng)確定，從而可以順利地進(jìn)行狀態(tài)轉(zhuǎn)移。

因此，我們定義狀態(tài)表dp如下：dp[i][j]表示從[i, j]位置出發(fā)，到達(dá)終點(diǎn)時(shí)所需的最低初始健康點(diǎn)數(shù)。

二、狀態(tài)轉(zhuǎn)移過(guò)程

在[i, j]位置，玩家有兩種選擇：向右走或向下走。我們需要根據(jù)這兩種選擇來(lái)推導(dǎo)dp[i][j]的值。

1. 向右走到達(dá)下一個(gè)位置，然后從該位置繼續(xù)到達(dá)終點(diǎn)。根據(jù)狀態(tài)定義，這要求我們?cè)赱i, j]位置的最低健康點(diǎn)數(shù)加上當(dāng)前位置的消耗，應(yīng)大于等于右邊位置的最低健康點(diǎn)數(shù)。即：x + dungeon[i][j] >= dp[i][j + 1]。通過(guò)移項(xiàng)，我們得到x的一個(gè)可能取值：x >= dp[i][j + 1] - dungeon[i][j]。

2. 向下走到達(dá)下一個(gè)位置，然后從該位置繼續(xù)到達(dá)終點(diǎn)。同樣地，我們要求[i, j]位置的最低健康點(diǎn)數(shù)加上當(dāng)前位置的消耗，應(yīng)大于等于下邊位置的最低健康點(diǎn)數(shù)。即：x + dungeon[i][j] >= dp[i + 1][j]。通過(guò)移項(xiàng)，我們得到x的另一個(gè)可能取值：x >= dp[i + 1][j] - dungeon[i][j]。

為了得到最小的初始健康點(diǎn)數(shù)，我們?nèi)∵@兩種情況下的最小值作為dp[i][j]的候選值。因此，狀態(tài)轉(zhuǎn)移方程為：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

然而，需要注意的是，如果當(dāng)前位置的dungeon[i][j]是一個(gè)較大的正數(shù)，那么dp[i][j]的值可能會(huì)變成0或負(fù)數(shù)，這意味著最低點(diǎn)數(shù)會(huì)小于1，導(dǎo)致玩家死亡。因此，我們需要對(duì)dp[i][j]進(jìn)行修正，確保其值至少為1。修正后的狀態(tài)轉(zhuǎn)移方程為：dp[i][j] = max(1, dp[i][j])。

三、初始化

為了正確地進(jìn)行狀態(tài)轉(zhuǎn)移，我們需要對(duì)dp表進(jìn)行初始化。一個(gè)常用的技巧是在dp表的最前面添加一行和一列輔助節(jié)點(diǎn)。這些輔助節(jié)點(diǎn)的值需要保證后續(xù)填表是正確的。在本題中，我們可以將所有輔助節(jié)點(diǎn)的值初始化為無(wú)窮大，然后設(shè)置dp[m][n - 1] = dp[m - 1][n] = 1，其中m和n分別是地圖的行數(shù)和列數(shù)。

四、填表順序

根據(jù)狀態(tài)轉(zhuǎn)移方程，我們需要從下往上逐行填寫(xiě)dp表，每行從左往右進(jìn)行填寫(xiě)。這樣的填表順序可以確保在計(jì)算每個(gè)位置的dp值時(shí)，其右側(cè)和下方的位置已經(jīng)計(jì)算完畢，從而可以利用這些已知值進(jìn)行狀態(tài)轉(zhuǎn)移。

五、返回值

最后，根據(jù)狀態(tài)表定義，我們需要返回dp[0][0]的值，即從起點(diǎn)出發(fā)到達(dá)終點(diǎn)時(shí)所需的最低初始健康點(diǎn)數(shù)。

3.代碼編寫(xiě)

class Solution 
{
public:
    int calculateMinimumHP(vector<vector<int>>& d) 
    {
        int m = d.size(), n = d[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
};

The Last

嗯，就是這樣啦，文章到這里就結(jié)束啦，真心感謝你花時(shí)間來(lái)讀。

覺(jué)得有點(diǎn)收獲的話，不妨給我點(diǎn)個(gè)贊吧！

如果發(fā)現(xiàn)文章有啥漏洞或錯(cuò)誤的地方，歡迎私信我或者在評(píng)論里提醒一聲~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-861595.html

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