动态规划之地下城问题

hello，my friend,今天，我给大家带来的是地下城问题，这个问题依旧属于动态规划问题，下面让我们来一起揭开它的神秘面纱吧

一.题目描述

这个题目很有意思！！讲的是在一个二维空间中，一个人想从左上角来到右下角，中间会经过很多空格，每一个空格中都有数字，数字小于零代表，代表进入这个空格将会损失的健康点数，数字大于零，代表将要获得的健康点数，如果健康点数小于零，那么这个人就会死。

举个例子

二.讲解算法原理

1.状态表示

状态表示的方式有两种：

第一种：dp[i][j]表示从起点出发到达[i][j]位置时，所需要的最低健康点数

第二种：dp[i][j]表示从[i][j]出发到达终点位置时，所需要的最低健康点数

本题，如果使用第一种方法，是做不出来的，

来看，[0][0]位置的最低健康点数应该是多少呢？？

假设是3,3-2=1；可以，但是无论是往下亦或是往右，都会死。

假设是5，但，试过会发现5也不行。

有人说5太小了，换个大点的，可以,100一定行，但还是最低吗？？所以根据这种方式，无法推导出状态转移方程。

在这里，只能使用第一种。

2.状态转移方程

[i][j]表示红圈，dp[i][j]表示到达此处所需要的最低健康点数，d[i][j]表示所消耗的点数，dp[i][j-1],dp[i-1][j]分别表示下边格和右边格所需要的最低健康点数。

所以

3.初始化

这个初始化方式和以往也不同，因为要求的是从起点[0][0]到终点的最低健康点数，所以，我们应该从下往上，从右向左的顺序进行初始化。

同时，我们也要解决越界问题，可以在原来的基础上，新增一行和一列

因为到达左下角的房间后，我们还得要出去，所以我们可以在如图所标注的位置设置为1，因为我们在比较下面方格和右边方格时，使用的是min，所以我们可以在其他的位置初始化为无穷大即可。

4.返回值

返回dp[0][0]即可。

三.代码实现