[LC 174]. Dungeon Game

开始尝试从左到右从上到下记录消耗掉点的最小值,结果陷入了无解。
[-2, -3, 3]
[-5, -10, 1]
[10, 30, -5]
应该从-2 –> -3 –> 3 –> 1 –> -5这条路径走,途中最大的消耗在最后一点(2,2)处,为-6,一共需要7点。路过30这条路虽然到最后需要的点数很少,但开始,例如-2 –> -5这一步消耗点就为-7,需要8点health。所以认为是在每一点算total cost的时候,取上面或左面最大cost最小的那个,一直算到右下最后一点,就可以知道可能用到的最小cost。

然后以下例子就不对了
[1, -3, 3]
[0, -2, 0]
[-3,-3,-3]
算到(1,2)这个位置时,total cost的情况是这样的:
[1, -2, 1]
[1, -1, X]
[X, X, X]
最大cost的情况是这样的:
[1, -2, -2]
[1, -1, X]
[X, X, X]
对(1,2)这点来说,上面来的一路最大cost是-2,左面一路最大cost是-1,所以选择左面一路似乎比较好,这样total cost最终是
[1, -2, 1]
[1, -1,-1]
[-2,-4,-4]
最终的cost是-4,需要5点health。但如果当初选择上面一路,(1,2)点total cost是1,最终点事-2,只需要3点health。所以选择最大cost最小的路径不一定得到正解,因为后面会因为这个选择产生更大的cost,但当初选择的时候并不知道。

这种情况出现的时候就应该意识到,需要倒序算出所需的最小cost。

用一个2D数组记录所需的最小health。在最终点的时候,需要health[m-1][n-1] + dungeon[m-1][n-1] >= 1, health[m-1][n-1] >= 1-dungeon[m-1][n-1]。注意所有的health[i][j]最少为1,如果小于1,证明在之前上一步就已经死了。所以,

health[m-1][n-1] = max(1, 1-dungeon[m-1][n-1])

其他的点health[i][j],需要health[i][j] + dungeon[i][j] >= min(health[i+1][j], health[i-1][j]),即算上初始的health,在算上进入(i,j)这间屋需要消耗的health,需要至少能到达右面和下面两个中需要health比较小的一个。所以

health[i][j] = max(1, min(health[i+1][j], health[i][j+1]) – dungeon[i][j])

如果i+1或j+1超出了范围,在调整上面公式,去掉health[i+1][j]或health[i][j+1].最后health[0][0]就是答案。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s