LeetCode-174. Dungeon Game(地下城游戏)(dp)

LeetCode-174. Dungeon Game(地下城游戏)(dp)

• 记忆化
• 二维dp
• 一维dp

题目链接

题目

这种题目都是一个套路，先写出递归，然后改dp或者记忆化，类似的题目有LeetCode62和LeetCode64

---

解析

记忆化

总共分为四中情况:

• 第一种就是最左下角;
• 第二种就是最后一行；
• 第三种就是最后一列；
• 第四种就是普通位置，依赖的位置是右边的和下面的；

具体解释看下图:

    public int[][] map;
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon.length <= 0 || dungeon[0].length <= 0)return 0;
        map = new int[dungeon.length][dungeon[0].length];
        return process(dungeon,0,0);
    }
    public int process(int[][] matrix,int i,int j){
        if(i == matrix.length - 1 && j == matrix[0].length - 1){
            return matrix[i][j] > 0 ? 1: -matrix[i][j] + 1;
        }
        if(map[i][j] != 0){
            return map[i][j];
        }
        if(i == matrix.length - 1){
            int R = process(matrix,i,j+1);
            map[i][j] = matrix[i][j] >= R ? 1 : R - matrix[i][j];
            return  map[i][j];
        }
        if(j == matrix[0].length - 1 ){
            int D  = process(matrix,i+1,j);
            map[i][j] = matrix[i][j] >= D ? 1 : D - matrix[i][j];
            return  map[i][j];
        }
        int min = Math.min(process(matrix,i,j+1),process(matrix,i+1,j));
        map[i][j] = matrix[i][j] >= min ? 1 :  min - matrix[i][j];
        return map[i][j];
    }

---

二维dp

至于从递归改成动态规划就是很套路的了。重点是写出递归。

 public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon.length <= 0 || dungeon[0].length <= 0)return 0;
        int n = dungeon.length,m = dungeon[0].length;
        int[][] dp = new int[n][m];
        dp[n-1][m-1] = dungeon[n-1][m-1] > 0 ? 1: - dungeon[n-1][m-1] + 1;
        for(int j = m - 2; j >= 0; j--)dp[n-1][j] =  dungeon[n-1][j] >= dp[n-1][j+1] ? 1 : dp[n-1][j+1] - dungeon[n-1][j];
        for(int i = n - 2; i >= 0; i--)dp[i][m-1] =  dungeon[i][m-1] >= dp[i+1][m-1] ? 1 : dp[i+1][m-1] - dungeon[i][m-1];
        for(int i = n-2; i >= 0; i--){
            for(int j = m-2; j >= 0; j--){
                dp[i][j] = (dungeon[i][j] >= Math.min(dp[i][j+1],dp[i+1][j])) ? 1 :  Math.min(dp[i][j+1],dp[i+1][j]) - dungeon[i][j];
            }
        }
        return dp[0][0];
    }

---

一维dp

因为位置依赖当前dp[j]还是dp[i+1][j]，dp[j+1][j+1]，所以只需要一个滚动数组。

 public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon.length <= 0 || dungeon[0].length <= 0)return 0;
        int n = dungeon.length,m = dungeon[0].length;
        int[] dp = new int[dungeon[0].length];
        dp[m-1] = dungeon[n-1][m-1] > 0 ? 1 : -dungeon[n-1][m-1] + 1;
        for(int j = m - 2; j >= 0; j--)dp[j] =  dungeon[n-1][j] >= dp[j+1] ? 1 : dp[j+1] - dungeon[n-1][j];
        for(int i = n - 2; i >= 0; i--){
            dp[m-1] = dungeon[i][m-1] >= dp[m-1] ? 1 : dp[m-1] - dungeon[i][m-1];
            for(int j = m - 2; j >= 0; j--){
                dp[j] = (dungeon[i][j] >= Math.min(dp[j+1],dp[j])) ? 1 : Math.min(dp[j+1],dp[j]) - dungeon[i][j];
            }
        }
        return dp[0];
    }