174.leetcode Dungeon Game

这个题目有点意思,最初我以为是动态规划,从左到右,从上到下一次扫一遍,然后到最后得到其中最小的值,到最后,我发现,这样不行,因为这个样子的dp有两个值需要维护,一个是到达i,j点的时候剩余的生命值left,一个是在到达i,j途遇到的最小的生命值min,在dp判断条件的时候,就会面临很判断的局面,比如{left= 10,min= -12,left = 1,min=-13},那两条路线中,那条才是最优的呢?显然根据终点的不同,优劣的评判也是不一样的,也就是说,正面dp是不行的。

放弃这个时候,开始想bfs,但是不行,因为每一步出去,都有两个选择,如果m= 100,n=100,这个矩阵不算大,然后bfs的复杂度就是2^(200)了,就算加上剪枝,不能达到目的。

网上标准的解法是从终点开始,维护到达终点时候,所需要的最小的生命值,最小值为1,这样就简单了很多,对于一个i,j来说,到达终点所需的最小生命值等于本房间内消耗的生命值   加  向右或者向下两条路上消耗的生命值的最小值,这样维护的值只有一个,可以进行dp了

Leave a comment

Your email address will not be published.

*