hello,my friend,今天,我给大家带来的是地下城问题,这个问题依旧属于动态规划问题,下面让我们来一起揭开它的神秘面纱吧
这个题目很有意思!!讲的是在一个二维空间中,一个人想从左上角来到右下角,中间会经过很多空格,每一个空格中都有数字,数字小于零代表,代表进入这个空格将会损失的健康点数,数字大于零,代表将要获得的健康点数,如果健康点数小于零,那么这个人就会死。
举个例子
状态表示的方式有两种:
第一种:dp[i][j]表示从起点出发到达[i][j]位置时,所需要的最低健康点数
第二种:dp[i][j]表示从[i][j]出发到达终点位置时,所需要的最低健康点数
本题,如果使用第一种方法,是做不出来的,
来看,[0][0]位置的最低健康点数应该是多少呢??
假设是3,3-2=1;可以,但是无论是往下亦或是往右,都会死。
假设是5,但,试过会发现5也不行。
有人说5太小了,换个大点的,可以,100一定行,但还是最低吗??所以根据这种方式,无法推导出状态转移方程。
在这里,只能使用第一种。
[i][j]表示红圈,dp[i][j]表示到达此处所需要的最低健康点数,d[i][j]表示所消耗的点数,dp[i][j-1],dp[i-1][j]分别表示下边格和右边格所需要的最低健康点数。
所以
这个初始化方式和以往也不同,因为要求的是从起点[0][0]到终点的最低健康点数,所以,我们应该从下往上,从右向左的顺序进行初始化。
同时,我们也要解决越界问题,可以在原来的基础上,新增一行和一列
因为到达左下角的房间后,我们还得要出去,所以我们可以在如图所标注的位置设置为1,因为我们在比较下面方格和右边方格时,使用的是min,所以我们可以在其他的位置初始化为无穷大即可。
返回dp[0][0]即可。