x*******i
发帖数: 26 | 1 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
直接贪婪做法肯定不行的。 | a*********2
发帖数: 194 | 2 DP？
假设初设strength为0，然后找从左上到右下角的最大strength。
结果路径最大，那么中间每一步都最大。
所以 f(i,j) = max( f(i-1,j), f(i,j-1) ) + grid(i,j) .
初始值f(0,1)=grid(0,1), f(1,0)=grid(1,0)，从(0,0)算到(n-1,m-1).
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| c*******u
发帖数: 1269 | 3 这个肯定和正负数分布有关，如果盘里只有一个正数那就是最开始需要很多strength
呀。
★ 发自iPhone App: ChineseWeb 7.8
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| P*******r
发帖数: 210 | 4 缺了当中每一步都大于0的条件
【在 a*********2 的大作中提到】
: DP？
: 假设初设strength为0，然后找从左上到右下角的最大strength。
: 结果路径最大，那么中间每一步都最大。
: 所以 f(i,j) = max( f(i-1,j), f(i,j-1) ) + grid(i,j) .
: 初始值f(0,1)=grid(0,1), f(1,0)=grid(1,0)，从(0,0)算到(n-1,m-1).
| c*******7
发帖数: 438 | 5 大概想了下，感觉DP的话每个格要保留的数据需要挺多才能不丢失信息。
设第一格为零，第一格开始做DP,每个格保留一个list，list里每个元素为某条路径的
当前体力值和路径最小体力值，list按照路径最小体力值排序。计算某一格新的list的
时候，merge左边格子和上面格子的两个list,去掉路径最小体力值小且当前体力值小的
元素。
到最后一格的时候找到当前体力值大于等于零且[路径最小体力值]的最小值 | y*****u
发帖数: 29 | 6 Maybe we can try two DPs.
In the 1st DP, suppose we have 0 strength at origin. We find the maximum
strength we can get at every point.
dp[i, j] += max(dp[i - 1, j], dp[i, j - 1]);
In the 2nd DP, we find the max of the min value on the 2 paths coming from
top and left.
dp[i, j] = min(max(dp[i - 1, j], dp[i, j - 1]), dp[i, j]); | b***e
发帖数: 1419 | 7 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)
)
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| g*****g
发帖数: 212 | 8 有了第一个DP的结果，沿着最大路径走回去（同时记录路径上的min）就可以了。
【在 y*****u 的大作中提到】
: Maybe we can try two DPs.
: In the 1st DP, suppose we have 0 strength at origin. We find the maximum
: strength we can get at every point.
: dp[i, j] += max(dp[i - 1, j], dp[i, j - 1]);
: In the 2nd DP, we find the max of the min value on the 2 paths coming from
: top and left.
: dp[i, j] = min(max(dp[i - 1, j], dp[i, j - 1]), dp[i, j]);
| a*********2
发帖数: 194 | 9 为什么要这个条件？
算出最大值是-10，那么最小所需要的能量就是10，以使得在终点处的能量至少为0.
【在 P*******r 的大作中提到】
: 缺了当中每一步都大于0的条件
| x*******i
发帖数: 26 | 10 这条路径中间有一步可能是-100，后面的给补回来90. 那最开始带10个就不够了
【在 a*********2 的大作中提到】
: 为什么要这个条件？
: 算出最大值是-10，那么最小所需要的能量就是10，以使得在终点处的能量至少为0.
| | | b***e
发帖数: 1419 | 11 所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。
【在 x*******i 的大作中提到】
: 这条路径中间有一步可能是-100，后面的给补回来90. 那最开始带10个就不够了
| x*******i
发帖数: 26 | 12 请大侠详细解释一下怎么控制呀
【在 b***e 的大作中提到】
: 所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。
| x*******i
发帖数: 26 | 13 请教下， 这个f() 和 w() 各自代表什么？
【在 b***e 的大作中提到】
: 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)
: )
| b***e
发帖数: 1419 | 14 f是dp函数的值，表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重，可以是正的或者负的。
【在 x*******i 的大作中提到】
: 请教下， 这个f() 和 w() 各自代表什么？
| t*****y
发帖数: 25 | 15 我的思路是这样，每一步需要计算两个变量,
f(i,j):从起点走到f(i,j)后能取得的能量和
g(i,j):在从走到f(i,j)的过程中，力量的最小值（整条旅途最艰难灰暗的时刻）
打个比方，哈利波特从(0,0)走到(i,j)的途径中，力量为10，-30，20，15，
那么 f(i,j) = 10 - 30 + 20 + 15 = 15, 而g(i,j) = -20.
这题的DP主要是求最后一个的g(i,j);如果g(i,j) < 0 那么输出为 -g(i,j), 反之输出
0.
DP的递推公式（要maximize g(i,j),选择一条不那么艰难的路哈）：
if g(i,j-1) <= g(i-1,j){
f(i,j) = f(i-1，j) + w(i,j)
g(i,j) = min(g(i-1,j),f(i,j)) // update旅途中最艰难时刻。
}else{
f(i,j) = f(i，j-1) + w(i,j)
g(i,j) = min(g(i,j-1),f(i,j))
} | X*4
发帖数: 101 | 16 这个好复杂
其实可以优化armstrong12的方法
假设初设strength为0，然后找从左上到右下角的最大strength。
结果路径最大，那么中间每一步都最大。
所以 f(i,j) = max( f(i-1,j), f(i,j-1) ) + grid(i,j) .
初始值f(0,1)=grid(0,1), f(1,0)=grid(1,0)，从(0,0)算到(n-1,m-1).
这个方法的问题在于 能保证 任何时刻如果你的strength > 0
先看一维的情况
-5 1 -3
armstrong12方法给出的结果 f[n-1] = grid[n] + f[n-1], 从后往前
f = [-7, -2, -3], 有的地方strength < 0, 所以不对
改进, 增加一个数目m, m[i]表示进入grid[i]之前需要的最小strength
grid[2] = -3.
所以要想保证 每步strength > 0, 进入grid[2]之前， strength 至少 > 3
m[i] = 3,
f = [,,0]
m = [,,3]
grid[1] = 1, 根据公式
f = [, 1, 0]
m = [, 3, 3]
grid[0] = -5
f[0] = -4, 要想保证 每步strength > 0, 进入grid[0]之前， strength 至少 > 4
所以
f = [0, 1, 0]
m = [7, 3, 3]
要求的结果就是7
所以1维下的递推公式是
grid, f, m
f[n] = max(0, grid[n] + f[n-1])
m[n] = -min(0, grid[n] + f[n-1]) + m[n-1]
当负数的时候，提供的补偿
返回m[0]
扩展到二维
不在边的情况下， j != N-1, i != M-1
到i,j可以从i-1,j 或i,j-1走
从i,j-1走， 有
f1[i][j] = max(0, grid[i][j] + f[i][j-1])
m1[i][j] = -min(0, grid[i][j] + f[i][j-1])
从i-1,j走， 有
f2[i][j] = max(0, grid[i][j] + f[i-1][j])
m2[i][j] = -min(0, grid[i][j] + f[i-1][j])
取m2[i][j]小得那条路
返回m[0][0]
【在 t*****y 的大作中提到】
: 我的思路是这样，每一步需要计算两个变量,
: f(i,j):从起点走到f(i,j)后能取得的能量和
: g(i,j):在从走到f(i,j)的过程中，力量的最小值（整条旅途最艰难灰暗的时刻）
: 打个比方，哈利波特从(0,0)走到(i,j)的途径中，力量为10，-30，20，15，
: 那么 f(i,j) = 10 - 30 + 20 + 15 = 15, 而g(i,j) = -20.
: 这题的DP主要是求最后一个的g(i,j);如果g(i,j) < 0 那么输出为 -g(i,j), 反之输出
: 0.
: DP的递推公式（要maximize g(i,j),选择一条不那么艰难的路哈）：
: if g(i,j-1) <= g(i-1,j){
: f(i,j) = f(i-1，j) + w(i,j)
| D*T
发帖数: 75 | 17 RE
我觉得这个算法应该是对的。
【在 t*****y 的大作中提到】
: 我的思路是这样，每一步需要计算两个变量,
: f(i,j):从起点走到f(i,j)后能取得的能量和
: g(i,j):在从走到f(i,j)的过程中，力量的最小值（整条旅途最艰难灰暗的时刻）
: 打个比方，哈利波特从(0,0)走到(i,j)的途径中，力量为10，-30，20，15，
: 那么 f(i,j) = 10 - 30 + 20 + 15 = 15, 而g(i,j) = -20.
: 这题的DP主要是求最后一个的g(i,j);如果g(i,j) < 0 那么输出为 -g(i,j), 反之输出
: 0.
: DP的递推公式（要maximize g(i,j),选择一条不那么艰难的路哈）：
: if g(i,j-1) <= g(i-1,j){
: f(i,j) = f(i-1，j) + w(i,j)
| g*****g
发帖数: 212 | 18 局部最优不表示全局最优
举个例子， A[n-1][m-1]是整个数组最小值（且远小于其他），也是终点
你要想避免这里力量降低最大，你只能前面积蓄足够力量
所以，这个根据g(i,j)贪婪的DP是不行的
不是选g(i,j)小的，而是选 f(i,j) 大的路径
【在 t*****y 的大作中提到】
: 我的思路是这样，每一步需要计算两个变量,
: f(i,j):从起点走到f(i,j)后能取得的能量和
: g(i,j):在从走到f(i,j)的过程中，力量的最小值（整条旅途最艰难灰暗的时刻）
: 打个比方，哈利波特从(0,0)走到(i,j)的途径中，力量为10，-30，20，15，
: 那么 f(i,j) = 10 - 30 + 20 + 15 = 15, 而g(i,j) = -20.
: 这题的DP主要是求最后一个的g(i,j);如果g(i,j) < 0 那么输出为 -g(i,j), 反之输出
: 0.
: DP的递推公式（要maximize g(i,j),选择一条不那么艰难的路哈）：
: if g(i,j-1) <= g(i-1,j){
: f(i,j) = f(i-1，j) + w(i,j)
| b***e
发帖数: 1419 | 19 似乎没有必要这么麻烦，用我前面的那个直接DP就行了。每个点计算当前点到目标的最
小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
况取最小作为当前点的最小能量要求即可。
【在 g*****g 的大作中提到】
: 局部最优不表示全局最优
: 举个例子， A[n-1][m-1]是整个数组最小值（且远小于其他），也是终点
: 你要想避免这里力量降低最大，你只能前面积蓄足够力量
: 所以，这个根据g(i,j)贪婪的DP是不行的
: 不是选g(i,j)小的，而是选 f(i,j) 大的路径
| D*T
发帖数: 75 | 20 搞了个例子：
A
[0, 0, -50, 2]
[1, -50, 100, 1]
[1, -1, -4, 0]
f
[0, 0, -50, -48]
[1, -49, 51, 52]
[2, 1, -3, -3]
g
[0, 0, 50, 50]
[0, 49, 49, 49]
[0, 0, 3, 3]
最优解起始HP是3就可以了。如果选f(i,j)大的路径，必然冲着100去，结果需要起始
HP50，不是最优解。
【在 g*****g 的大作中提到】
: 局部最优不表示全局最优
: 举个例子， A[n-1][m-1]是整个数组最小值（且远小于其他），也是终点
: 你要想避免这里力量降低最大，你只能前面积蓄足够力量
: 所以，这个根据g(i,j)贪婪的DP是不行的
: 不是选g(i,j)小的，而是选 f(i,j) 大的路径
| | | g*****g
发帖数: 212 | 21 不好意思，之前没仔细看，
似乎目前为止，只有你的是对的。
f(0,0) 为所求
【在 b***e 的大作中提到】
: 似乎没有必要这么麻烦，用我前面的那个直接DP就行了。每个点计算当前点到目标的最
: 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
: 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
: 况取最小作为当前点的最小能量要求即可。
| g*****g
发帖数: 212 | 22 我想说的是，最小“左上cost”和最大“左上sum”的dp都不对，
应该只有blaze的那个DP算法是对的
给两个例子，证明之前两个算法是错的：
例子1：
0 0 0 0
0 0 -6 0
0 -5 20 0
0 0 0 1
例子2：
0 0 0 0
0 0 -6 0
0 -5 20 0
0 0 0 -10
【在 D*T 的大作中提到】
: 搞了个例子：
: A
: [0, 0, -50, 2]
: [1, -50, 100, 1]
: [1, -1, -4, 0]
: f
: [0, 0, -50, -48]
: [1, -49, 51, 52]
: [2, 1, -3, -3]
: g
| D*T
发帖数: 75 | 23 public static int minStartingStrength(int[][] A) {
int m = A.length;
if (m==0) {
return 0;
}
int n= A[0].length;
if (n==0) {
return 0;
}
int[][] f = new int[m][n];
int[][] g = new int[m][n];
f[0][0] = A[0][0];
g[0][0] = f[0][0]<0 ? -f[0][0] : 0;
for (int i=1;i
f[i][0] = f[i-1][0] + A[i][0];
g[i][0] = f[i][0] <0 ? Math.max(-f[i][0], g[i-1][0]) : g[i-1][0];
}
for (int j=1;j
f[0][j] = f[0][j-1] + A[0][j];
g[0][j] = f[0][j] <0 ? Math.max(-f[0][j], g[0][j-1]) : g[0][j-1];
}
for (int i=1;i
for (int j=1;j
if (g[i-1][j]
f[i][j] = f[i-1][j] + A[i][j];
g[i][j] = Math.max(g[i-1][j], -f[i][j]);
}
else {
f[i][j] = f[i][j-1] + A[i][j];
g[i][j] = Math.max(g[i][j-1], -f[i][j]);
}
}
}
return g[m-1][n-1];
}
这两个例子都没问题。第一个是0，第二个是10。
估计两种算法都是对的。
【在 g*****g 的大作中提到】
: 我想说的是，最小“左上cost”和最大“左上sum”的dp都不对，
: 应该只有blaze的那个DP算法是对的
: 给两个例子，证明之前两个算法是错的：
: 例子1：
: 0 0 0 0
: 0 0 -6 0
: 0 -5 20 0
: 0 0 0 1
: 例子2：
: 0 0 0 0
| S*A
发帖数: 7142 | 24 这个方法我一开始也是用类似思路的，但是我后来发现这个是不能直接用最短路径的
算法的。你的算法只记录当前点到目标的最少能量是不够的。
任何一条指定的路径，其实是有两个属性。一个是最小能量 M (越小越好），
另外一个是累计能量S（越大约好）。这两个是独立的，任何给定的 M，S，
我可以构造出一个路径满足这个条件。其实就是第一步是 －M， 第二步是 M＋ S。
现在有两条路径 1， 2 可以同时到达某一点。
如果是最短路径，其中一个路径可以完全舍弃，因为只有一个衡量标准就是S。
长的完全废掉。这个点只需要记得他的上一个节点就可以了。
但是现在加了一维数，如果 M1 < M2, S1 > S2 的情况，路径1 完胜 路径2，
路径2 可以废除。
如果出现 M1 < M2 但是 S1 < S2 的不完胜情况，你就没法舍弃其中一个。
因为完全取决于后面的路径是什么。如果后面是个很大的负数，你就要用 S2。
因为大的 S2 可以抵消掉一部分负数胜出。如果后面不是很大的负数，那路径1
有比较小 M1 胜出。
所以搜素的时候，不同路径到达同一个中间点是不能完全合并的，只有上面提
到的完胜情况可以合并，不是完胜两种不同的到达路径都要保留。所以每个中间
点有一个路径的 list。这样搜素空间其实比最短路径大了很多。
如果新的路径 M，S 被 list 里面的已经有的 （Mi，Si） 完胜，就不用加到 list 里
面。
否则加到 list 里面。如果 list 里面有被 M，S 完胜的 （Mi， Si），就需要剔
除出去。
然后不是一个路径到达终点就结束，要等其他合并后的路径也到达终点。
我举例一个矩阵，你的算法会挑 －1，＋1，－6 最小要 6
最优是 －3， ＋10， －6 最小要 3.
＋00 －03 ＋10 －99
－01 －99 ＋00 －99
＋01 ＋00 ＋00 －6
－99 －99 －99 0
【在 b***e 的大作中提到】
: 似乎没有必要这么麻烦，用我前面的那个直接DP就行了。每个点计算当前点到目标的最
: 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
: 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
: 况取最小作为当前点的最小能量要求即可。
| S*A
发帖数: 7142 | 25 补充一下，我的例子是从左上开始搜素。从右下的话要调整一下。 | l******6
发帖数: 340 | 26
cool perspective
【在 b***e 的大作中提到】
: 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)
: )
| S*A
发帖数: 7142 | 27 这个没有考虑累计 strength 我觉得应该是不对的，看我上面的例子。
【在 l******6 的大作中提到】
:
: cool perspective
| w*******s
发帖数: 138 | 28 你这个例子blaze的算法也是正确的。
你所解释的是为什么很多从出发点开始推到目的点的算法是错误的，但是blaze的方法是
从目的地开始倒推回出发点，这个方法比我之前想到的二分答案要简单很多。这题似乎
只能倒推。
【在 S*A 的大作中提到】
: 这个方法我一开始也是用类似思路的，但是我后来发现这个是不能直接用最短路径的
: 算法的。你的算法只记录当前点到目标的最少能量是不够的。
: 任何一条指定的路径，其实是有两个属性。一个是最小能量 M (越小越好），
: 另外一个是累计能量S（越大约好）。这两个是独立的，任何给定的 M，S，
: 我可以构造出一个路径满足这个条件。其实就是第一步是 －M， 第二步是 M＋ S。
: 现在有两条路径 1， 2 可以同时到达某一点。
: 如果是最短路径，其中一个路径可以完全舍弃，因为只有一个衡量标准就是S。
: 长的完全废掉。这个点只需要记得他的上一个节点就可以了。
: 但是现在加了一维数，如果 M1 < M2, S1 > S2 的情况，路径1 完胜 路径2，
: 路径2 可以废除。
| S*A
发帖数: 7142 | 29 修改： 倒退好像是可以的，让我再想想。
－－－－－－－－－－－－－－－－－－－
倒推把我的矩阵转180 度，调整 ＋－ 的次序就可以了。
我分析的道理是一样的。关键问题是不能单单用最小能量来合并
路径。
法是
【在 w*******s 的大作中提到】
: 你这个例子blaze的算法也是正确的。
: 你所解释的是为什么很多从出发点开始推到目的点的算法是错误的，但是blaze的方法是
: 从目的地开始倒推回出发点，这个方法比我之前想到的二分答案要简单很多。这题似乎
: 只能倒推。
| S*A
发帖数: 7142 | 30 从后面向前找是对的，佩服啊。
从后面累计的体力就没有用了，因为反正到终点剩多少体力
没有关系。只需要最少体力就可以了。
那路径的确可以合并，就是后面向前的最短路径问题。
blaze 的思路很对。我怎么就没有想到呢。 | | | w*******s
发帖数: 138 | 31 看来做题的时候需要不停的变换思路啊
【在 S*A 的大作中提到】
: 从后面向前找是对的，佩服啊。
: 从后面累计的体力就没有用了，因为反正到终点剩多少体力
: 没有关系。只需要最少体力就可以了。
: 那路径的确可以合并，就是后面向前的最短路径问题。
: blaze 的思路很对。我怎么就没有想到呢。
| m*****k
发帖数: 731 | 32 w(i,j)没有用？
那w(0,0)岂不是与结果无关？
这样得出的f(0,0)是离开（0,0）的strength， 还不是harry potter 的值吧。
【在 b***e 的大作中提到】
: 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)
: )
| m*****k
发帖数: 731 | 33 sorry, 看题不仔细， HP already at (0,0) from very beginning.
【在 m*****k 的大作中提到】
: w(i,j)没有用？
: 那w(0,0)岂不是与结果无关？
: 这样得出的f(0,0)是离开（0,0）的strength， 还不是harry potter 的值吧。
| r****c
发帖数: 2585 | 34 blaze倒退有简介又对，正面来是不对的
为什么呢，因为求的是从起始点开始所有路径里面min max。新加了一个点在后面的话
，即使你找到了相邻的min max，但是这个点自己是有weight的，而且这个weight在最
后，如果weight很小的话完全可以和以前的min max无关。往回退就不一样了，因为min
max是从第一个点算起的，只要找到零界点就可以了， | b***e
发帖数: 1419 | 35 语体教？
min
【在 r****c 的大作中提到】
: blaze倒退有简介又对，正面来是不对的
: 为什么呢，因为求的是从起始点开始所有路径里面min max。新加了一个点在后面的话
: ，即使你找到了相邻的min max，但是这个点自己是有weight的，而且这个weight在最
: 后，如果weight很小的话完全可以和以前的min max无关。往回退就不一样了，因为min
: max是从第一个点算起的，只要找到零界点就可以了，
| m**********g
发帖数: 153 | 36 靠，百撕不得其姐， 而大侠却一枪中的， 人与人的差距咋就这么大呢。
【在 b***e 的大作中提到】
: 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)
: )
| P**H
发帖数: 1897 | 37 从终点到起点，反过来DP。一次就够了。
【在 m**********g 的大作中提到】
: 靠，百撕不得其姐， 而大侠却一枪中的， 人与人的差距咋就这么大呢。
| m****c
发帖数: 252 | 38 backtrack, 一次DP就搞定了。
这个题目类似于crack the coding interview 8.2 题。 | e********3
发帖数: 18578 | 39 Backtrack, recursive, and dynamic programming.
Here is the code (changes size to see the solution for matrices of different
sizes), the time complexity is O(n) (n = size*size) and the memory usage is
O(n) as well:
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMap
Integer>();
static class CacheKey{
public int x, y;
public CacheKey(int x, int y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj){
CacheKey key = (CacheKey) obj;
return this.x == key.x && this.y == key.y;
}
@Override
public int hashCode(){
return ((Integer) (this.x+this.y)).hashCode();
}
}
public static int[][] createMatrix(int width, int height){
int[][] matrix = new int[height][width];
for (int i=0; i
for (int j=0; j
matrix[i][j] = rand.nextInt(50);
if (rand.nextBoolean()){
matrix[i][j] *= -1;
}
}
}
return matrix;
}
public static void printMatrix(int[][] matrix){
for (int i=0; i
int j = 0;
for (; j
System.out.print(matrix[i][j] + ", ");
}
System.out.println(matrix[i][j]);
}
}
public static int minimumStrength(int x, int y){
int strength = 0;
if (x == matrix[0].length-1 && y == matrix.length-1){
if (matrix[y][x] < 0){
strength = -1 * matrix[y][x];
}
} else if (x == matrix[0].length-1){
int nextStrength = cachedStrength(x, y+1);
strength = calcStrength(nextStrength, x, y);
} else if (y == matrix[0].length-1){
int nextStrength = cachedStrength(x+1, y);
strength = calcStrength(nextStrength, x, y);
} else {
int nextStrength = Math.min(cachedStrength(x, y+1),
cachedStrength(x+1, y));
strength = calcStrength(nextStrength, x, y);
}
System.out.println(x + ", " + y + " needs minimum strength of " +
strength);
return strength;
}
public static int cachedStrength(int x, int y){
CacheKey key = new CacheKey(x, y);
if (cache.containsKey(key)){
return cache.get(key);
} else {
int strength = minimumStrength(x, y);
cache.put(key, strength);
return strength;
}
}
private static int calcStrength(int nextStrength, int x, int y){
int strength = 0;
if (nextStrength == 0){
if (matrix[y][x] < 0) strength = -1 * matrix[y][x];
} else {
if (matrix[y][x] - nextStrength >= 0){
strength = 0;
} else {
strength = nextStrength - matrix[y][x];
}
}
return strength;
}
public static void main(String []args){
int size = 5;
matrix = createMatrix(size,size);
printMatrix(matrix);
cachedStrength(0,0);
}
}
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| A*********c
发帖数: 430 | 40 This concludes the discussion.
确实就是path sum的简单变形。
个人觉得这个两行的解法之后没有任何继续讨论的必要了。
【在 b***e 的大作中提到】
: 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)
: )
| | | b*******g
发帖数: 57 | 41 blaze的算法基本没有问题，但是否忽略了起点和终点也有可能失血呢？
比如对于这样的grid
-5 0 0 0
0 0 -6 0
0 2 0 0
0 0 0 -3
【在 A*********c 的大作中提到】
: This concludes the discussion.
: 确实就是path sum的简单变形。
: 个人觉得这个两行的解法之后没有任何继续讨论的必要了。
| l**********a
发帖数: 181 | | f**********t
发帖数: 1001 | 43 int harryPotterGrid(vector &grid, size_t col) {
if (grid.empty() || col == 0) {
return 0;
}
size_t row = grid.size() / col;
if (row == 0) {
return 0;
}
vector strengths(grid.size());
strengths[row * col - 1] = 0;
for (size_t i = row - 1; ; --i) {
for (size_t k = col - 1; ; --k) {
size_t x = i * col + k;
if (i + 1 != row) {
size_t xx = (i + 1) * col + k;
strengths[x] = 1 + strengths[xx] - grid[xx];
}
if (k + 1 != col) {
strengths[x] = min(strengths[x], 1 + strengths[x + 1] - grid[x + 1]);
}
if (k == 0) break;
}
if (i == 0) break;
}
return strengths[0];
}
void harryPotterGridTest() {
vector grid{3,-5,1,4,-9,2,-11,-1,-8};
cout << harryPotterGrid(grid, 3) << endl; | a******w
发帖数: 317 | 44 典型dp吧
最简单就是画个一样大矩阵
死了的格不能往下走
如果空间大小是concern,
保留两行就够
或者跟对角线一样长。有点自找麻烦
还是两行比较好
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| a******w
发帖数: 317 | 45 哦看错题了
那就从右下往左上走
保留每格最小值？
F(I,j)=min(下，右）- strength(I,j)
小于0清0。
【在 a******w 的大作中提到】
: 典型dp吧
: 最简单就是画个一样大矩阵
: 死了的格不能往下走
: 如果空间大小是concern,
: 保留两行就够
: 或者跟对角线一样长。有点自找麻烦
: 还是两行比较好
| c*****w
发帖数: 50 | 46 DP seems not work because history dependent path, use variation of Dijkstra
(similar to bottleneck shortest path)
【在 x*******i 的大作中提到】
: 假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
: 正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
: 么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
: 初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。
| t*******y
发帖数: 22 | 47 should be
f(i, j) = min(
: max(f(i+1, j) - w(i+1,j), 1),
: max(f(i, j+1) - w(i, j+1), 1)
? | s***5
发帖数: 2136 | 48 这个解法有问题。任何路径如果出现非正元素即作废，所以dp完成后，必须从（0,0）
搜索是否有全正路径到（m，n）。
一开始倒退着做dp时，应该把所有非正元素也保存。如果回溯的时候发现有全正路径，
f(0,0)即是答案。否则要找一条替代路径，可以用最小代价c使其转为全正路径，这样
答案就是f(0,0)+c。
【在 b***e 的大作中提到】
: 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)
: )
| P****i
发帖数: 1362 | 49 blaze的是正解
【在 g*****g 的大作中提到】
: 不好意思，之前没仔细看，
: 似乎目前为止，只有你的是对的。
: f(0,0) 为所求
| S********s
发帖数: 29 | 50 example code of blaze's solution:
import java.util.Arrays;
import java.util.Random;
/*
* http://www.mitbbs.com/article_t1/JobHunting/32611137_0_1.html
*/
public class HarryPotMatrix {
Integer[][] w;
Integer m, n;
Integer[][] f;
public void initialize(int i, int j) {
Random r = new Random();
m = i;
n = j;
w = new Integer[m][n];
for (int l = 0; l < m; l++) {
for (int h = 0; h < n; h++) {
w[l][h] = -1 * r.nextInt(20);
}
}
System.out.println(Arrays.deepToString(w));
}
public void initialize(Integer[][] matrix) {
w = matrix;
m = matrix.length;
n = matrix[0].length;
f = new Integer[m][n];
System.out.println(Arrays.deepToString(w));
}
private Integer move(int i, int j) {
if (f[i][j] != null)
return f[i][j];
if (i == m - 1 && j == n - 1) {
f[i][j] = 0;
return 0;
}
Integer result = null;
// can move right?
boolean right = false;
if (i < m && j + 1 < n)
right = true;
// can move down?
boolean down = false;
if (i + 1 < m && j < n)
down = true;
if (right == true && down == false)
result = Math.max(move(i, j + 1) - w[i][j + 1], 0);
else if (down == true && right == false)
result = Math.max(move(i + 1, j) - w[i + 1][j], 0);
else if (down == true && right == true)
result = Math.min(Math.max(move(i, j + 1) - w[i][j + 1], 0),
Math.max(move(i + 1, j) - w[i + 1][j], 0));
else if (down == false && right == false)
result = 0;
f[i][j] = result;
return result;
}
public Integer initialVale() {
move(0, 0);
System.out.println(Arrays.deepToString(f));
int offset = w[0][0] < 0 ? -w[0][0] : 0;
return f[0][0] + offset;
}
public static void main(String[] args) {
HarryPotMatrix hpm = new HarryPotMatrix();
// hpm.initialize(5, 4);
// Integer[][] matrix = { { -5, 0, 0, 0 }, { 0, 0, -6, 0 },
// { 0, 2, 0, 0 }, { 0, 0, 0, -3 } };
Integer[][] matrix = { { 0, -3, 10, -99 }, { -1, -99, 0, -99 },
{ 1, 0, 0, -6 }, { -99, -99, -99, 0 } };
hpm.initialize(matrix);
System.out.println(hpm.initialVale());
}
} | | | l*******0
发帖数: 95 | 51 这个就是求“路径和”最大值maxSum的问题，所需点数： maxSum >= 0 ? 0 : maxSum
* -1;
State: state[i][j] 表示从(0,0)到(i,j)的路径最大值，
init: state[0][0] = A[0][0],
state[0][i] = state[0][i-1] + A[0][i] for i = 1...n-1
state[i][0] = state[i-1][0] + A[i][0] for i = 1...n
DP function: state[i]j] = MAX(state[i-1][j], state[i][j-1]) + A[i][j]
result: state[n-1][n-1] >= 0 ? 0 : state[n-1][n-1] * -1; |
|
