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

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

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

為了盡快到達(dá)公主，騎士決定每次只向右或向下移動一步。

編寫一個函數(shù)來計算確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。

例如，考慮到如下布局的地下城，如果騎士遵循最佳路徑 右 -> 右 -> 下 -> 下，則騎士的初始健康點(diǎn)數(shù)至少為 7。

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

說明:

騎士的健康點(diǎn)數(shù)沒有上限。

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

思路：

動態(tài)規(guī)劃，dp[i][j]代表行進(jìn)到(i,j)時候剩余的健康點(diǎn)數(shù)，若要行進(jìn)到下一個點(diǎn)，則要加上當(dāng)前點(diǎn)dungeon[i][j]。因為只能往右或者往下移動，所以dp[i][j]=min(dp[i][j+1]-dungeon[i][j],dp[i+1][j]-dungeon[i][j])。此外，還要考慮邊界條件的限制，在最下面和最右邊時候min只有一項，還有就是dp[i][j]的最小值是1，需要加上對負(fù)數(shù)的判斷。具體實現(xiàn)代碼如下。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        if(!dungeon.size() || !dungeon[0].size())
        {
            return 0;
        }
        int rows=dungeon.size();
        int cols=dungeon[0].size();
        vector<vector<int>> dp;
        dp=vector<vector<int>>(rows,vector<int>(cols,0));
        for(int i=rows-1;i>=0;i--)
        {
            for(int j=cols-1;j>=0;j--)
            {
                if(i==rows-1 && j==cols-1)
                {
                    dp[i][j]=max(1,1-dungeon[i][j]);
                }
                else if(i==rows-1)
                {
                    dp[i][j]=max(dp[i][j+1]-dungeon[i][j],1);
                }
                else if(j==cols-1)
                {
                    dp[i][j]=max(dp[i+1][j]-dungeon[i][j],1);
                }
                else
                {
                    int h1=max(dp[i][j+1]-dungeon[i][j],1);
                    int h2=max(dp[i+1][j]-dungeon[i][j],1);
                    dp[i][j]=min(h1,h2);
                }
            }
        }
        return dp[0][0];
    }
};