动态规划之地下城游戏

痛定思痛。 2024-03-16 23:00 6阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [地下城游戏][Link 1]  
![image.png][]  
一开始看到这么多文字, 头都大了. 下面就来根据示例的图帮助理解一下  
![image.png][image.png 1]  
**骑士每次只能向右或者向下走一步**, 我们可以倒推一下示例的路线, 很容易就可以知道  
![image.png][image.png 2]

## 2. 状态表示 ##

按照我们往常的经验, 肯定是以 ( i, j ) 位置为结尾, 表示从起点到 ( i, j ) 位置时的所需的初始最低血量. 现根据这个状态表示我们来推导一下状态转移方程

还是根据最近的一步来进行划分.  
![image.png][image.png 3]  
还是一样, 求解到达 ( i, j ) 位置时的最低初始血量需要先求解到达 ( i, j-1 ) 的最低初始血量 dp\[i, j-1\] 和 到达 ( i-1, j ) 时的最低初始血量.

但是这有一个问题, 到达 ( i, j ) 位置的初始血量不仅仅受到 ( i, j-1 ) 位置和 ( i-1, j ) 位置的影响. 什么意思呢 ? 还是结合示例 1 来讲解 :  
![image.png][image.png 4]  
**终点的最低血量不仅仅搜到画红圈的 1 和 30 的两个位置的最低血量影响. 还受到画绿色圈的影响**. 它是有很多条不同路径的. 进入任何一个房间击败不了恶魔都需要重设起始点的初始血量. 因此此时的状态表示以某个位置结尾时从起始点到达该位置的最低初始血量就无法推导出状态转移方程了. **因为它收到的影响不仅仅是两个方向的.**

那么, 这种表示方法行不通, 我们还有一种经验方法, 也就是以 ( i, j ) 位置为起点, 表示从 ( i, j ) 位置开始到达终点时所需要的最低初始血量.

## 3. 状态转移方程 ##

以 i, j ) 位置为起点, 表示从 ( i, j ) 位置开始到达终点时所需要的最低初始血量. 推导此时的状态转移方程 dp\[i\]\[j\] : 还是以最近的一步来划分问题  
![image.png][image.png 5]

1.  从 ( i, j ) 位置出发往 ( i, j+1 ) 位置走

什么时候才能从 ( i, j ) 位置正确进入到 ( i, j + 1 ) 位置呢 ? 假设 ( i, j ) 位置此时最低初始血量为 X, **当 X + dungeon\[i\]\[j\] >= dp\[i\]\[j+1\] 时才能有机会到达终点. 题目要求最低初始血量, 取等时即可**

**dp 表里存的是从某个位置出发时的最低血量. 此时这个位置的最低血量为 X, 想要走出这个位置就需要先击败里面的恶魔 dungeon\[i\]\[j\], 之后剩余血量 X + dungeon\[i\]\[j\] 也就是此时进入 ( i, j+1 ) 的最低初始血量必须要大于等于 ( i, j+1 ) 的最低初始血量 dp\[i\]\[j+1\] 才能进入, 否则无法到达终点.**

**此时 X = dp\[i\]\[j+1\] - dungeon\[i\]\[j\]**

1.  从 ( i, j ) 位置出发往 ( i+1, j ) 位置走

同理, 从 ( i, j ) 位置出发往 ( i+1, j ) 想要到达终点所需要的最低初始血量为 dp\[i+1\]\[j\] - dungeon\[i\]\[j\]

由于我们求的是从某点出发到终点的最低初始血量, 最终 **dp\[i\]\[j\] = Math.min(dp\[i\]\[j+1\], dp\[i+1\]\[j\] )** **- dungeon\[i\]\[j\]**

PS :**有一点是需要注意的, 当 dungeon\[i\]\[j\] 非常大的时候, dp\[i\]\[j\] 最终是一个小于 0 的数. 这是什么意思 ?**

也就是当你进入 ( i, j ) 位置时, 这里面是一个非常大的血包 dungeon\[i\]\[j\] 此时我进入 ( i, j ) 位置时自身血量哪怕是负数最终也可以进入到 ( i, j+1 ) 位置. 这是不合理的, 负数就应该直接死亡. **必须保证在进入 ( i, j ) 位置时它的血量大于 0 才行.**

**因此我们需要对最终的 dp\[i\]\[j\] 进行处理. dp\[i\]\[j\] = Math.max( 1, dp\[i\]\[j\] ). 也就是进入某处时的最低初始血量必须是大于 0 才能进入 !**

## 4. 初始化 ##

根据状态转移方程, 想要计算从 ( i, j ) 位置出发到达终点时的最低初始血量, 就需要先计算它的前一个位置和下一个位置的最低初始血量. 因此以下位置在填表时不进行初始化就会导致填表发生越界错误.  
![image.png][image.png 6]  
因此, 这些位置在进行填表之前, 都是我们需要进行初始化的. 同样, 我们还是采取新增一行一列的办法, 将初始化的内容放在填表当中. 但此时不是和之前一样, 左边添加一列上面添加一行, **而是下面添加一行最后面添加一列**  
![image.png][image.png 7]

1.  当填写这个位置的值时

由于它受到向右和向下两个位置的最小初始血量影响. 但是这两个位置是我们新开的. 它不应该影响我们要填的这个位置的值.

如果要填的这个红星的位置值为 0 的话, 显然是不对的. 这意味着你从这个地方出发的最低初始血量是 0, 而我们上面说了最低初始血量至少是 1. **而我们想要向右走或者向左走, 进去的最低血量就是 1, 可以理解为救完人后, 出来的最低血量至少是 1**. 因此这两个位置的初始化结果为 1  
![image.png][image.png 8]

1.  填写其他位置的值时

当初始化其他位置的时候,**这个时候要填写的位置除了受到新增位置的影响还受到原本矩阵内容的影响. 而我们新增的这些位置不能影响原本的数据.** 根据状态转移方程取得是这两个方向上值的最小值. 因此新增的位置的值初始化为无穷大就不会影响我们填写的最终结果了.  
![image.png][image.png 9]

## 5. 填表顺序 ##

可以看到, 填写 ( i, j ) 位置时, 需要依赖它的后一个和下一个位置的值. 因此我们填表的顺序为 **从下到上填写每一行, 而每一行又从右往左填写**

## 6. 返回值 ##

题目要求返回到达 ( m, n ) 位置时的最低初始血量. 而我们的状态表示为从某个位置开始到达终点时所需要的最低初始血量. 也就是 dp\[0\]\[0\].

## 7. 代码演示 ##

class Solution {
        
        public int calculateMinimumHP(int[][] dungeon) {
        
    
            // 1. 创建 dp 表
            int m = dungeon.length;
            int n = dungeon[0].length;
            int[][] dp = new int[m + 1][n + 1];
    
            // 2. 初始化 
            // 将最后一行初始化为无穷大
            for(int j = 0; j <= n; j++) {
        
                dp[m][j] = Integer.MAX_VALUE;
            }
            // 将最后一列初始化为无穷大
            for(int i = 0; i <= m; i++) {
        
                dp[i][n] = Integer.MAX_VALUE;
            }
            // 将终点的右边和下边位置初始化为 1
            dp[m][n - 1] = dp[m - 1][n] = 1;
    
            // 3. 填写 dp 表, 从下往上每一行, 每一行从右往左
            for(int i = m - 1; i >= 0; i--) {
        
                for(int j = n - 1; j >= 0; j--) {
        
    
                    // 根据状态转移方程填写
                    // 虽然多开了一行一列, 但是对应到原本的 dungeon 的位置没变. 
                    // 因为添加的位置是在最后一行和最后一列.
                    dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j] ) - dungeon[i][j];
    
                    // 如果最终的结果太小为负数, dp 表中表示某个位置为起点的最低初始血量至少大于 1
                    // 因此要对这个最终结果进行处理
                    dp[i][j] = Math.max(1, dp[i][j]);
                }
            }
            
            // 4. 确认返回值
            return dp[0][0];
        }
    }

[Link 1]: https://leetcode.cn/problems/dungeon-game/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a248ac35293c4307ad716254905f7a68.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/adc86f4e3baa4f49a7271313a3dc8301.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0075b053ee5341f28c86e4fc9bc19520.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e3200d63e82b4573867eddd4d1de9909.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b2c5c12728d74652ac50297ad0a901c0.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c2929f07f4014a62824a6892ae005888.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6f9d3e58bbf54b919e2bfdd97d02ef75.png
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9e74312219e54ff089568ba6a18388c2.png
[image.png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/940330b7c5c64ff9a7c79225af81fff9.png
[image.png 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0373c72f3f7b4425a77e278d0dbb45b8.png