“趣味”or“烧脑”算法之王子救公主

水深无声 2023-06-13 06:28 35阅读 0赞

## | 题引 ##

相信大部分人童年都玩过大富豪这样一类的棋，棋格上面有加多少分，减多少分等等设置，比赛最终谁的分值最多（类似下面这个棋盘）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70]

--------------------

## | 正题 ##

设置小游戏为一个二维矩阵，  
王子位于左上角，公主位于右下角，  
每个单元格将会出现怪物或者补给

怪物：打斗减血（负数表示，且为整数）  
补给：加血（正数表示，且为整数）

王子只能往下或者往右前进，  
如果王子血量为0或负数，即为拯救失败，  
求王子至少需要多少初始血量，才能抵达公主？  
![在这里插入图片描述][20191114201621681.png]  
最优解： -2 — -3 — 3 — 1 — -5 需要初始血量为7

--------------------

## | 分析 ##

先分析题目的重点：

*  只能往右或着往下前进
 *  任意步只要血量掉0即失败（也就意味每步结束后血量至少保持1点）
 *  每步可能加血、减血，或者不变（为0时）

分析完重点，来看一些场景  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 1]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 2]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 3]

--------------------

看完3个小场景后，按常规思路，总结一个小规律  
**往下往右的时候，判断下和右的大小前进**

那么这个结论是不是正确的呢，再来看下面一个场景…

--------------------

![在这里插入图片描述][20191114202833433.png]  
按照上面总结的规律，得出这样的结论，如果细心的去计算的话，发现并不是最优解，虽然第一步的时候-3，但是+5之后，立马又回血了，正确的最优解如下：  
![在这里插入图片描述][20191114203032408.png]

--------------------

至此，说明上面的小规律总结并不成立，那么就说明从正面打通思路就不行了，那么就逆向思维看看是否有解决办法？

**再分析：**  
从后往前计算，计算当我达到这步的时候，应该需要多少血量（**为了方便计算，我们计算每步的临界值，即到达这步血量为0，最终结果+1即可**）

以场景4为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 4]  
计算到“王子”位置时，结果为2，表示王子位置出发，必须至少需要2+1=3血量

**总结一下：**

*  逆向思维倒推，从后往前计算每步至少血量
 *  最右和最下边，可通过下面或后面的值，再与当前棋格的值计算可得出至少血量
 *  中间部分可通过相邻的右边和下边值判断出，再与当前棋格的值计算可得出至少血量

**计算顺序逻辑图如下：**  
![在这里插入图片描述][20191114204305547.png]

--------------------

## |编码 ##

分析了这么多，我们按照分析思路去编码实现（**小伙伴们可以自己先尝试编码看看**）

/** * @author yanghao * @version LeetCode174Test.java, v 0.1 2019-11-12 16:43 */
    public class LeetCode174Test { 
    
        public static void main(String[] args) { 
            LeetCode174Test test = new LeetCode174Test();
    
            /*int[][] dungeon = new int[3][3]; dungeon[0] = new int[]{-2, -3, 3}; dungeon[1] = new int[]{-5, -10, 1}; dungeon[2] = new int[]{10, 30, -5};*/
    
            /*int[][] dungeon = new int[3][3]; dungeon[0] = new int[]{1,-3,3}; dungeon[1] = new int[]{0,-2,0}; dungeon[2] = new int[]{-3,-3,-3};*/
    
            int[][] dungeon = new int[3][3];
            dungeon[0] = new int[]{ 1, -3, 5};
            dungeon[1] = new int[]{ 0, -5, 0};
            dungeon[2] = new int[]{ -3, -3, 1};
    
            /*int[][] dungeon = new int[2][2]; dungeon[0] = new int[]{2, 1}; dungeon[1] = new int[]{1, -1};*/
    
            /*int[][] dungeon = new int[2][2]; dungeon[0] = new int[]{0, 5}; dungeon[1] = new int[]{-2, -3};*/
    
            /*int[][] dungeon = new int[2][1]; dungeon[0] = new int[]{2}; dungeon[1] = new int[]{1};*/
    
            /*int[][] dungeon = new int[2][1]; dungeon[0] = new int[]{1}; dungeon[1] = new int[]{-1};*/
    
            /*int[][] dungeon = new int[2][3]; dungeon[0] = new int[]{3, -20, 30}; dungeon[1] = new int[]{-3, 4, 0};*/
    
            /*int[][] dungeon = new int[3][1]; dungeon[0] = new int[]{1}; dungeon[1] = new int[]{-2}; dungeon[2] = new int[]{1};*/
    
            /*int[][] dungeon = new int[1][2]; dungeon[0] = new int[]{0, 0};*/
    
            System.out.println(test.leetCode174(dungeon));
    
        }
    
        public int leetCode174(int[][] dungeon) { 
            int x = dungeon[0].length;
            int y = dungeon.length;
    
            if (dungeon == null || x == 0 || y == 0) { 
                return 0;
            }
    
            //定义一个矩阵存储每格需要的血量，从后往前推算每格最少需要多少血量
            int[][] blood = new int[y][x];
            //填充最后一格
            blood[y - 1][x - 1] = Math.max(0, -dungeon[y - 1][x - 1]);
            //定义所需最少血量
            int lowBlood = 0;
    
            //填充最后一行
            for (int i = x - 2; i >= 0; i--) { 
                lowBlood = blood[y - 1][i + 1] - dungeon[y - 1][i];
                blood[y - 1][i] = Math.max(0, lowBlood);
            }
    
            //填充最后一列
            for (int i = y - 2; i >= 0; i--) { 
                lowBlood = blood[i + 1][x - 1] - dungeon[i][x - 1];
                blood[i][x - 1] = Math.max(0, lowBlood);
            }
    
            //填充中间部分
            for (int i = x - 2; i >= 0; i--) { 
                for (int j = y - 2; j >= 0; j--) { 
                    lowBlood = Math.min(blood[j][i + 1], blood[j + 1][i]) - dungeon[j][i];
                    blood[j][i] = Math.max(0, lowBlood);
                }
            }
    
            return blood[0][0] + 1;
    
        }
        
    }

--------------------

## |赠语 ##

**学习算法，思想很重要，要学会突破常规思路**  
（本题尝试了很多解决思路，这个算是比较优的解决办法，当然还可以通过其他方式去实现，小伙伴们尽情发挥自己的大脑吧，本题目来自LeetCode 174题，题目为了易懂，稍作精简改编）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191114201503549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA==,size_16,color_FFFFFF,t_70
[20191114201621681.png]: https://img-blog.csdnimg.cn/20191114201621681.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191114202127233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191114202140893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191114202207778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA==,size_16,color_FFFFFF,t_70
[20191114202833433.png]: https://img-blog.csdnimg.cn/20191114202833433.png
[20191114203032408.png]: https://img-blog.csdnimg.cn/20191114203032408.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191114203637900.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2ODIzNA==,size_16,color_FFFFFF,t_70
[20191114204305547.png]: https://img-blog.csdnimg.cn/20191114204305547.png