Q:
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
A:
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)
)
所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重，可以是正的或者负的。
每个点计算当前点到目标的最
小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
况取最小作为当前点的最小能量要求即可。
No comments:
Post a Comment