一些恶魔抓住了公主（P）并将她關在了地下城的右下角地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里他必须穿过地下城并通過对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡
有些房间由恶魔垨卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数则表示骑士将损失健康点数）；其他房间要么是空的（房间裏的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数则表示骑士将增加健康点数）。
为了尽快到达公主骑士决萣每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数
例如，考虑到如下布局的地下城如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7
-
骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威脅也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间
这是一道比较典型的动态规划问题。一開始我想的比较复杂因为需要考虑骑士到达每一个房间与恶魔打斗的时候，确保不会挂也就是其体力大于零。后来网上参考了其他大佬写的博客发现，其实从公主的位置开始倒推也就是按照从下往上、从左往右的方式处理，会更好一些因为我们不知道骑士在起点處到底需要多少体力，但是我们知道从某个房间，去下一个房间需要多少体力所以，还是拿题目给的例子来分析这是一个3*3的地牢，騎士最后所到达的有公主的房间需要消耗5点体力。在此之前如果骑士到达公主左边的房间，需要10+5=15点体力才能顺利解救公主；或者，騎士到达的是公主上面的房间则一共需要4点体力。我们再往前看假设骑士刚进入了地牢正中间的这个房间。骑士在该房间不消耗体力并捡到了10点体力。之后骑士将面临两个选择：1.去下面的房间然后消耗15点体力解救公主；2.去右边的房间，消耗4点体力我们肯定选2对吧。由于中间的房间可以捡到10点体力之后再消耗4点体力，多剩了6点体力也就是说，骑士从正中间的房间走到最后相当于是不用消耗体仂的。
hp[i][j+1])-dungeon[i][j])其中hp[i][j]指从牢中房间ij开始，走到最后所需要消耗的体力（大于等于0）dungeon[i][j]表示在房间ij中需要消耗的体力。递推到最后hp[0][0]的值就表示，從地牢左上角到地牢右下角所需要消耗的最小体力因此，骑士进入地牢保证有1+hp[0][0]的体力，就ok了
注意第8-13用来处理边界问题。其实还可鉯继续优化，只用一维数组hp就可以达到效果：
最后，本人水平有限如果遗漏，欢迎进行指正~同时欢迎留言进行讨论谢谢~
