设置小游戏为一个二维矩阵，
王子位于左上角，公主位于右下角，
每个单元格将会出现怪物或者补给
怪物：打斗减血（负数表示，且为整数）
补给：加血（正数表示，且为整数）
王子只能往下或者往右前进，
如果王子血量为0或负数，即为拯救失败，
求王子至少需要多少初始血量，才能抵达公主？
最优解： -2 — -3 — 3 — 1 — -5 需要初始血量为7
| 分析
先分析题目的重点：
- 只能往右或着往下前进
- 任意步只要血量掉0即失败（也就意味每步结束后血量至少保持1点）
- 每步可能加血、减血，或者不变（为0时）
分析完重点，来看一些场景
看完3个小场景后，按常规思路，总结一个小规律
往下往右的时候，判断下和右的大小前进
那么这个结论是不是正确的呢，再来看下面一个场景…
按照上面总结的规律，得出这样的结论，如果细心的去计算的话，发现并不是最优解，虽然第一步的时候-3，但是+5之后，立马又回血了，正确的最优解如下：
至此，说明上面的小规律总结并不成立，那么就说明从正面打通思路就不行了，那么就逆向思维看看是否有解决办法？
再分析：
从后往前计算，计算当我达到这步的时候，应该需要多少血量（为了方便计算，我们计算每步的临界值，即到达这步血量为0，最终结果+1即可）
以场景4为例：
计算到“王子”位置时，结果为2，表示王子位置出发，必须至少需要2+1=3血量
总结一下：
逆向思维倒推，从后往前计算每步至少血量
最右和最下边，可通过下面或后面的值，再与当前棋格的值计算可得出至少血量
中间部分可通过相邻的右边和下边值判断出，再与当前棋格的值计算可得出至少血量
计算顺序逻辑图如下：
|编码
分析了这么多，我们按照分析思路去编码实现（小伙伴们可以自己先尝试编码看看）
|赠语
学习算法，思想很重要，要学会突破常规思路
我自己是一名从事了多年开发的JAVA老程序员，今年年初我花了一个月整理了一份最适合2019年学习的java学习干货，可以送给每一位喜欢java的小伙伴，想要获取的可以关注我的头条号并在后台私信我：【交流】，即可免费获取。
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.sosokankan.com/article/1425603.html