最小路徑和（medium）
64. 最小路徑和
? 給定一個包含非負整數的 m x n 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。
? **說明：**每次只能向下或者向右移動一步。
示例 1：
輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小。
示例 2：
輸入：grid = [[1,2,3],[4,5,6]]
輸出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
解題思路
? 首先還是狀態表示，依照路徑問題的經驗和題目要求，可以很容易的設定 dp[i][j] 表示到達 [i, j] 位置時的最小路徑和。
? 接著就是狀態轉移方程，根據最近一步來推導的話，和 [i, j] 有關系的就是 [i-1, j] 和 [i, j-1] 這兩格了，以前者為例，dp[i-1][j] 表示到達 [i-1, j] 位置時候的最小路徑和，那么 dp[i, j] 想得到最小路徑和，不就是 用 [i-1, j] 的最小路徑和，加上 [i, j] 當前的大小 嗎，很簡單明了，對于 [i, j-1] 也同樣如此！
? 既然要的是最小的路徑和，我們只需要取 dp[i-1][j] 和 dp[i][j-1] 中小的那個加上當前的大小即可！
? 所以狀態轉移方程為：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
? 然后還是初始化問題，因為我們要給表格加上虛擬行列，并且因為我們的狀態轉移方程是根據左邊和上邊格子得到的，這樣子的話我們只需要多加一行一列，放在最上邊和最左邊這一行一列作為虛擬行列！
? 現在考慮兩個問題，①虛擬行列的初始值不能影響后面填表的正確；②下標的映射關系。
? 其實最重要的還是第一個，因為我們在左上角開始遍歷，需要讓 dp[1][1] 得到的還是原來 gird 中的值，所以 得讓 dp[0][1] 或者 dp[1][0] 為 0，保證加的時候加 0，就不會有影響了，而 其它位置都設為 INT_MAX，因為其它邊界位置其實是不想收到這個虛擬行列的影響的，只希望收到附近的非虛擬位置的影響，所以用 INT_MAX 的時候進行最小值判斷就不會取到它了！
? 填表順序就是從上往下，從左往右！
? 最后返回的就是右下角的值也就是到達右下角的最小路徑和！
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 多開一行一列給虛擬行列，都設為INT_MAXdp[0][1] = 0; // 初始化虛擬位置for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];}}return dp[m][n];}
};
地下城游戲（hard）
174. 地下城游戲
? 惡魔們抓住了公主并將她關在了地下城 dungeon 的 右下角 。地下城是由 m x n 個房間組成的二維網格。我們英勇的騎士最初被安置在 左上角 的房間里，他必須穿過地下城并通過對抗惡魔來拯救公主。
? 騎士的初始健康點數為一個正整數。如果他的健康點數在某一時刻降至 0 或以下，他會立即死亡。
? 有些房間由惡魔守衛，因此騎士在進入這些房間時會失去健康點數（若房間里的值為負整數，則表示騎士將損失健康點數）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點數的魔法球（若房間里的值為正整數，則表示騎士將增加健康點數）。
? 為了盡快解救公主，騎士決定每次只 向右 或 向下 移動一步。
? 返回確保騎士能夠拯救到公主所需的最低初始健康點數。
**注意：**任何房間都可能對騎士的健康點數造成威脅，也可能增加騎士的健康點數，包括騎士進入的左上角房間以及公主被監禁的右下角房間。
示例 1：
輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
輸出：7
解釋：如果騎士遵循最佳路徑：右 -> 右 -> 下 -> 下 ，則騎士的初始健康點數至少為 7 。
示例 2：
輸入：dungeon = [[0]]
輸出：1
提示：
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
解題思路
? 這道題乍一看和上面幾道路徑題好像差不多，但其實這道題隱藏很多細節，稍不注意就出錯，至少我是這樣子的！為什么這么說呢???
? 按我們上面做題的經驗來看，我們都是以 [i, j] 為結尾怎么這么樣這種情況，但是在這道題中，這種狀態表示其實是不正確的，是推導不出來的，我們來舉個例子：
? 注意：上圖中的例子只是為了表達這種狀態表示是錯誤的，其實例子的一些細節是錯誤的，注意即可！
? 所以我們就得改變一下思考方式，考慮從后面往前推導，也就是說以 [i, j] 為起點怎么怎么樣這種情況，其實通過后面講解會看到這樣子是行得通的！
? 所以我們的狀態表示 dp[i][j] 表示以 [i, j] 為起點，到達終點也就是右下角的最低健康點數！
? 也就是說現在我們推導的就是 dp[0][0] 了，那么就得 從后往前推導。
?
? 接著就是狀態轉移方程，既然是從后往前推導，那么肯定是和當前格子的右邊或者下邊有關系。解釋如下圖：
? 除此之外，上圖中還解釋了初始化的問題，并且我們并不需要去關心下標映射的問題，因為我們的虛擬行列是開在最后一行和最后一列！
? 填表的順序的話，就是從下往上，每行從右往左！
? 返回值就是左上角的值！
?
這樣子就結束了嗎???
? 結束就錯了，還有一個細節我們沒有處理！仔細想一下上面的狀態轉移方程，其中是涉及到了減法，要是遇到一種情況，就是 dungeon[i][j] 是一個正數，也就相當于這道題的一個加血點，如果它很大，導致減完之后得到的是一個負數，那么 dp[i][j] 是一個負數肯定是錯誤的啊，它表示的是最小健康點數，小于等于 0 不就掛了嗎對不對！
? 所以我們必須處理一下，為了讓其減去一個很大的負數之后還能得到一個最小的健康點數，我們想到的就是 1，所以我們在執行完狀態轉移方程之后還必須做一次判斷，或者直接處理這個數，使得 dp[i][j] 不會成為一個負數，如果是負數了，就讓它變成最小的健康點數 1 即可，代碼如下：
dp[i][j] = max(1, dp[i][j]);
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size();int n = dungeon[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 加入虛擬行列dp[m][n-1] = 1; // 將右下角的最近一步初始化為1，這樣子的話保證了初始健康點數的q'z// 從下往上，從右往左填表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];}
};
)
