算法原理

1. 狀態(tài)表示

• 我們之前在動(dòng)態(tài)規(guī)劃的算法中說(shuō)過(guò)，遇到動(dòng)態(tài)規(guī)劃問(wèn)題時(shí)，一般的解決方式就是分兩種情況：
• • （1） 選擇某一個(gè)位置為終點(diǎn)結(jié)束，建立dp表，進(jìn)行狀態(tài)表示
• • （2）選擇某一個(gè)位置為起點(diǎn)出發(fā)…
• 按照常規(guī)思路，我們既然知道了公主的位置，那正常情況就是選擇第一種情況來(lái)試著進(jìn)行狀態(tài)表示
• 這道題如果我們照著這個(gè)思路定義成：從起點(diǎn)開(kāi)始，到達(dá)[i, j] 位置的時(shí)候，所需的最低初始健康點(diǎn)數(shù)。
• 那么我們分析狀態(tài)轉(zhuǎn)移的時(shí)候會(huì)有?個(gè)問(wèn)題：那就是我們當(dāng)前的健康點(diǎn)數(shù)還會(huì)受到后面的路徑的影響。也就是從上往下的狀態(tài)轉(zhuǎn)移不能很好地解決問(wèn)題。

這里是為什么呢？我們?cè)O(shè)想一下，假設(shè)此時(shí)我們騎士的血很少，下一格無(wú)論是朝下還是朝右都會(huì)遇到惡魔把我們騎士的血扣為負(fù)數(shù)，那此時(shí)這里的dp值合理嗎？很顯然是不合理的。因此我們出了考慮前面位置的情況，還要考慮后面路徑的情況，豈不是太麻煩了？

• 這個(gè)時(shí)候我們要換?種狀態(tài)表示：從[i, j] 位置出發(fā)，到達(dá)終點(diǎn)時(shí)所需要的最低初始健康點(diǎn)數(shù)。這樣我們?cè)诜治鰻顟B(tài)轉(zhuǎn)移的時(shí)候，前面的路徑不需要考慮，后續(xù)的最佳狀態(tài)已經(jīng)知曉，這樣就極大的簡(jiǎn)化了我們分析的難度。

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

2 狀態(tài)轉(zhuǎn)移方程

• 對(duì)于 dp[i][j] ，從 [i, j] 位置出發(fā)，下?步會(huì)有兩種選擇（為了方便理解，設(shè) dp[i][j] 的最終答案是 x）：

• i. ?到右邊，然后?向終點(diǎn)

• 那么我們?cè)?[i, j] 位置的最低健康點(diǎn)數(shù)加上這?個(gè)位置的消耗，應(yīng)該要?于等于右邊位置的最低健康點(diǎn)數(shù)，也就是： x + dungeon[i][j] >= dp[i][j + 1] 。
  通過(guò)移項(xiàng)可得： x >= dp[i][j + 1] - dungeon[i][j] 。因?yàn)槲覀円氖亲?值，因此這種情況下的 x = dp[i][j + 1] - dungeon[i][j] ；

• ii. ?到下邊，然后?向終點(diǎn)

• 那么我們?cè)?[i, j] 位置的最低健康點(diǎn)數(shù)加上這?個(gè)位置的消耗，應(yīng)該要?于等于下邊位置的最低健康點(diǎn)數(shù)，也就是： x + dungeon[i][j] >= dp[i + 1][j] 。
  通過(guò)移項(xiàng)可得： x >= dp[i + 1][j] - dungeon[i][j] 。因?yàn)槲覀円氖亲?值，因此這種情況下的 x = dp[i + 1][j] - dungeon[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] 的值可能變成 0 或者負(fù)數(shù)。也就是最低點(diǎn)數(shù)會(huì)?于 1 ，那么騎?就會(huì)死亡。因此我們求出來(lái)的 dp[i][j] 如果?于等于 0 的話，說(shuō)明此時(shí)的最低初始值應(yīng)該為 1 。處理這種情況僅需讓 dp[i][j] 與 1 取?個(gè)最?值即可：
  dp[i][j] = max(1, dp[i][j])

什么意思呢？就是這里的[i,j]會(huì)給恢復(fù)一大口血，但是如果此時(shí)的dp[i,j]為負(fù)數(shù)的時(shí)候，說(shuō)明此時(shí)這里要求的騎士的最低血量是0或者負(fù)數(shù)，這顯然是不符合要求的，因此我們需要對(duì)這種特殊情況進(jìn)行一下上述的這種處理

初始化

• 可以在最前?加上?個(gè)「輔助結(jié)點(diǎn)」，幫助我們初始化。使?這種技巧要注意兩個(gè)點(diǎn)：
• i. 輔助結(jié)點(diǎn)??的值要「保證后續(xù)填表是正確的」；
• ii. 「下標(biāo)的映射關(guān)系」。

有關(guān)輔助節(jié)點(diǎn)的使用方法在上面鏈接的博客中講過(guò)了，這里就不再詳敘

• 在本題中，由于我們要考慮后面路徑對(duì)現(xiàn)在位置的影響，需要在dp表最后面添加一行，并且添加?列后，所有的值都先初始化為無(wú)窮大，然后讓dp[m][n - 1] 或dp[m - 1][n] = 1 即可。

填表順序

• 根據(jù)「狀態(tài)轉(zhuǎn)移方程」，我們需要「從下往上填每一行」，「每一行從右往左填」?？戳松厦娴乃惴ǚ治鲞@一點(diǎn)應(yīng)該不難理解

返回值

• 從題目中可知，我們的騎士是從左上角開(kāi)始的，因此結(jié)合上述分析，我們需要返回的值為dp[0][0]

編寫(xiě)代碼

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m=dungeon.size();
        int n=dungeon[0].size();
        //建立dp表，以某個(gè)位置為開(kāi)始建立狀態(tài)轉(zhuǎn)移方程
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[m][n-1]=1;//考慮邊界問(wèn)題
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
            	//填表
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=max(1,dp[i][j]);
            }
        }
        //返回值
        return dp[0][0];

    }
};

• 代碼很簡(jiǎn)單，只有十幾行，實(shí)際上難的是上面分析題目的過(guò)程以及對(duì)一些特殊情況的判斷，代碼這里相信如果你能看懂上述原理的分析，這點(diǎn)對(duì)你來(lái)說(shuō)應(yīng)該一點(diǎn)都不難。

總結(jié)

• 好啦，我們今天的內(nèi)容就先到這里啦！其實(shí)代碼并不重要，能看懂背后隱藏的原理并且通過(guò)這個(gè)題目學(xué)會(huì)對(duì)應(yīng)題目的分析才重要，因此如果你想真正學(xué)會(huì)的話，不妨自己從頭試著理解一下算法原理再自己獨(dú)立編寫(xiě)代碼，這樣我相信是最能提升自己有關(guān)動(dòng)態(tài)規(guī)劃題目的理解的。
• 有任何的問(wèn)題和對(duì)文章內(nèi)容的疑惑歡迎在評(píng)論區(qū)中提出，當(dāng)然也可以私信我，我會(huì)在第一時(shí)間回復(fù)的?。?/font>