Harry Potter walk on a 2D matrix

This was copied from http://www.mitbbs.com/article_t1/JobHunting/32611137_0_1.html
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。

直接贪婪做法肯定不行的。

 
发信人: blaze (狂且), 信区: JobHunting
标  题: Re: G家题讨论： harry potter 走矩阵
 发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)

Just dp:

 f(m, n) = 0

 f(i, j) = min(
   max(f(i+1, j) - w(i+1,j), 0),
   max(f(i, j+1) - w(i, j+1), 0)
 )


发信人: blaze (狂且), 信区: JobHunting
标  题: Re: G家题讨论： harry potter 走矩阵
 发信站: BBS 未名空间站 (Mon Jan 20 04:22:10 2014, 美东)

f是dp函数的值，表示从当前的点走到目标最少需要多少能量。

w是当前点上的权重，可以是正的或者负的。

每个点计算当前点到目标的最
 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
 况取最小作为当前点的最小能量要求即可。