leetcode: 174.地下城游戏（动态规划）

链接：https://leetcode-cn.com/problems/dungeon-game/
这道题最主要的问题是自顶向下的动态规划是不正确的，一定要采取自底向上的模式。
java代码：

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int dp[][] = new int [dungeon.length][dungeon[0].length];//dp[i][j]表示从（i,j）到右下角所需的生命值
        for(int i = dungeon.length-1;i>=0;i--)
        {
            for(int j = dungeon[0].length-1;j>=0;j--)
            {
                if(i==dungeon.length-1&&j==dungeon[0].length-1)
                    dp[i][j] = Math.max(1,1-dungeon[i][j]);
                else if (i==dungeon.length-1)
                {
                    dp[i][j] = Math.max(1,dp[i][j+1]-dungeon[i][j]);
                }
                else if(j==dungeon[0].length-1)
                    dp[i][j] = Math.max(1,dp[i+1][j]-dungeon[i][j]);
                else 
                {
                    dp[i][j] = Math.min(Math.max(1,dp[i+1][j]-dungeon[i][j]), Math.max(1,dp[i][j+1]-dungeon[i][j]));//向右走或向下走取一个小的值
                }
            }
        }
        return dp[0][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24