LeetCode 174. Dungeon Game

Problem

LeetCode 174. Dungeon Game

力扣174. 地下城游戏

1. 题目简述

有一个m * n的矩阵，每个格子内有数字（有正有负）。勇士从矩阵的左上角出发，每次只能向右或者向下行动一步，目的地是矩阵右下角。如果要保证到达右下角时，勇士的血量大于0，那么勇士的初始血量最低为多少。

注:

1. 骑士的健康点数没有上限。
2. 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2(起点)	-3	3
-5	-10	1
-10	30	-5(终点)

2. 算法思路

DP