地下城游戲

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

狀態(tài)表示：
按照以往題的表示，dp[i][j]表示：從起點（0，0）位置到達（i，j）位置時，所需的最小初始健康值。但是如果這么去表示，不僅要考慮到達（i，j）位置的最小初始健康值，由于魔法球的存在，還需要考慮到達（i，j）位置時的健康值，因為魔法球會對算后續(xù)位置的最小初始健康值產(chǎn)生影響

下面用題目中的示例1為例，演示:

由此可知，到達魔法球位置所需的最低初始健康值和上一次的最低初始健康值保持一致，而魔法球會增加健康值，這就會對后面的結果產(chǎn)生影響，因此我們不僅要考慮到達（i，j）位置的最小初始健康值，還需要考慮到達（i，j）位置時的健康值，以保證后續(xù)結果的正確性

因此，我們可以試著用dp[i][j]表示：以（i，j）位置為起點，到達終點位置時，所需的最小健康值。當(i,j)位置是魔法球時，可以用之前的dp[i+1][j]和dp[i][j+1]中的最小健康值減去治療量，就能得到當前的位置到達終點位置時所需的最小健康值dp[i][j]（注意：dp[i][j]不能小于0，最小值為1)；當(i,j)位置是惡魔時，也是這樣處理，實際上就是加上了需要扣除的健康值

通過這種狀態(tài)表示，我們最終能夠求得結果！

總結：

1. 這道題的難點在于怎么去處理健康值增加的問題，健康值的增加不能為之前的損失提供幫助，只會對后續(xù)有幫助
2. 如果按照第一種狀態(tài)表示，dp[i][j]僅僅只表示了從（0，0）位置到達（i，j）位置所需的最小初始健康值，而由于魔法球的存在，導致后續(xù)的健康值會增加，因此我們還需要去記錄當前位置的健康值，以保證后續(xù)計算最小初始健康值的正確性
3. 如果按照第二種狀態(tài)表示，dp[i][j]表示從（0，0）位置出發(fā)，按照最優(yōu)路徑到達（i，j）位置時，還需要剩余的最小健康值（為了到達終點后，健康值為1）。即dp[i][j]不僅表示了從（i，j）位置到達終點位置所需的最小初始健康值，還表示了從（0，0）位置出發(fā)到達（i，j）位置時，所需剩余的最小健康值（即當前健康值）
4. 比較兩種狀態(tài)表示，可知，第二種表示更合理，更方便后續(xù)的填表

狀態(tài)轉移方程
dp[i][j] = min(dp[i+1][j],dp[i][j+1])-d[i][j]，dp[i][j] = max(1, dp[i][j])

初始化
創(chuàng)建表時，多創(chuàng)建一行(第m行)和一列（第n列），除dp[m][n-1] = 1（dp[m-1][n] 也可初始化為1，表示救出公主后還需剩余1點健康值），其他都初始化為正無窮(以防對填表產(chǎn)生影響)

填表順序
從下往上，每一行從右往左

返回值
dp[0][0]

實現(xiàn)代碼

class Solution {public int calculateMinimumHP(int[][] dungeon) {//1.創(chuàng)建dp表int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m+1][n+1];//2.初始化for(int row = 0; row < m+1; row++) {dp[row][n] = Integer.MAX_VALUE;}for(int col = 0; col < n+1; col++) {dp[m][col] = Integer.MAX_VALUE;}dp[m][n-1] = 1;//3.填表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]);}}//4.返回值return dp[0][0];}
}