leetcode 174. Dungeon Game | 174. 地下城游戏（暴力递归-＞傻缓存-＞dp）

男娘i 2022-09-14 09:07 107阅读 0赞

## 题目 ##

[https://leetcode.com/problems/dungeon-game/][https_leetcode.com_problems_dungeon-game]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

#### 方法1：4个参数的递归+缓存，TLE ####

今日结论：转换成dp之前，递归的参数设计很重要，参数越少越好

我第一版递归有4个参数，心想，加个缓存吧，当我写出4个map嵌套的时候，内心是绝望的。。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 方法2：两个参数的dp ####

方法 1 超时，于是看了答案的递归版本：  
[https://leetcode.com/problems/dungeon-game/discuss/745340/post-Dedicated-to-beginners-of-DP-or-have-no-clue-how-to-start][https_leetcode.com_problems_dungeon-game_discuss_745340_post-Dedicated-to-beginners-of-DP-or-have-no-clue-how-to-start]

然后用 暴力递归->傻缓存->dp 的套路，转化成的自底向上的 dp。

class Solution { 
        int M, N;
    
        public int calculateMinimumHP(int[][] dungeon) { 
            M = dungeon.length;
            N = dungeon[0].length;
            int[][] dp = new int[M + 1][N + 1];
            
            // 【Solution 1】傻缓存
           // return process(0, 0, dungeon, dp);
            
            // 【Solution 2】dp
            for (int i = 0; i <= M; i++) { 
                dp[i][N] = Integer.MAX_VALUE;
            }
            for (int i = 0; i <= N; i++) { 
                dp[M][i] = Integer.MAX_VALUE;
            }
            dp[M - 1][N - 1] = dungeon[M - 1][N - 1] > 0 ? 1 : 1 - dungeon[M - 1][N - 1];
            for (int i = M - 1; i >= 0; i--) { 
                for (int j = N - 1; j >= 0; j--) { 
                    if (i == M - 1 && j == N - 1) continue;
                    int p1 = dp[i + 1][j];
                    int p2 = dp[i][j + 1];
                    int minReq = Math.min(p1, p2) - dungeon[i][j];
                    dp[i][j] = minReq <= 0 ? 1 : minReq;
                }
            }
            return dp[0][0];
        }
    
        // return min requirement
        // public int process(int i, int j, int[][] dungeon, int[][] dp) { 
        // if (i == M || j == N) return Integer.MAX_VALUE;
        // if (dp[i][j] != 0) return dp[i][j];
        // if (i == M - 1 && j == N - 1) { 
        // return dungeon[i][j] > 0 ? 1 : 1 - dungeon[i][j];
        // } else { 
        // int p1 = process(i + 1, j, dungeon, dp);
        // int p2 = process(i, j + 1, dungeon, dp);
        // int minReq = Math.min(p1, p2) - dungeon[i][j];
        // dp[i][j] = minReq <= 0 ? 1 : minReq;
        // return dp[i][j];
        // }
        // }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_dungeon-game]: https://leetcode.com/problems/dungeon-game/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c0c48a01dd0042539e8b56bfb82c0d85.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/993ef7502d7c4822a20b3789d3ec39dc.png
[https_leetcode.com_problems_dungeon-game_discuss_745340_post-Dedicated-to-beginners-of-DP-or-have-no-clue-how-to-start]: https://leetcode.com/problems/dungeon-game/discuss/745340/post-Dedicated-to-beginners-of-DP-or-have-no-clue-how-to-start
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/5e331e99b09b45a88bb0292732ccfd7e.png