A Primer on Valuation Models - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

A Primer on Valuation Models

A Primer on Valuation Models# Stock

x*i2010-02-17 08:02

1 楼

假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
直接贪婪做法肯定不行的。

j*u2010-02-17 08:02

2 楼

大家来吃午餐吧
20个
呵呵，顺便聊聊天

l*r2010-02-17 08:02

3 楼

【以下文字转载自 Trading_System 俱乐部】
发信人: liliwater (lyrist), 信区: Trading_System
标题: A Primer on Valuation Models
发信站: BBS 未名空间站 (Wed Feb 17 19:02:27 2010, 美东)
www.team-sys.com/primer.pdf

a*22010-02-17 08:02

4 楼

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最少是多少，才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。

h*u2010-02-17 08:02

5 楼

竟然在出门前赶上了。哈哈

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

e*n2010-02-17 08:02

6 楼

ding

【在 l*******r 的大作中提到】

: 【以下文字转载自 Trading_System 俱乐部】
: 发信人: liliwater (lyrist), 信区: Trading_System
: 标题: A Primer on Valuation Models
: 发信站: BBS 未名空间站 (Wed Feb 17 19:02:27 2010, 美东)
: www.team-sys.com/primer.pdf

c*u2010-02-17 08:02

7 楼

这个肯定和正负数分布有关，如果盘里只有一个正数那就是最开始需要很多strength
呀。

★ 发自iPhone App: ChineseWeb 7.8

【在 x*******i 的大作中提到】

o*o2010-02-17 08:02

8 楼

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

P*r2010-02-17 08:02

9 楼

缺了当中每一步都大于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).

e*b2010-02-17 08:02

10 楼

吃!

c*72010-02-17 08:02

11 楼

大概想了下，感觉DP的话每个格要保留的数据需要挺多才能不丢失信息。
设第一格为零，第一格开始做DP,每个格保留一个list，list里每个元素为某条路径的
当前体力值和路径最小体力值，list按照路径最小体力值排序。计算某一格新的list的
时候，merge左边格子和上面格子的两个list,去掉路径最小体力值小且当前体力值小的
元素。
到最后一格的时候找到当前体力值大于等于零且[路径最小体力值]的最小值

b*02010-02-17 08:02

12 楼

ha
pai

y*u2010-02-17 08:02

13 楼

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]);

t*g2010-02-17 08:02

14 楼

pai 包子.

b*e2010-02-17 08:02

15 楼

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 的大作中提到】

j*u2010-02-17 08:02

16 楼

呵呵，不敬业，我是赶回来的
看看我的小白鼠的报告

【在 h*********u 的大作中提到】

: 竟然在出门前赶上了。哈哈

g*g2010-02-17 08:02

17 楼

有了第一个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]);

e*a2010-02-17 08:02

18 楼

同吃!

a*22010-02-17 08:02

19 楼

为什么要这个条件？
算出最大值是-10，那么最小所需要的能量就是10，以使得在终点处的能量至少为0.

【在 P*******r 的大作中提到】

: 缺了当中每一步都大于0的条件

a*n2010-02-17 08:02

20 楼

re

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

x*i2010-02-17 08:02

21 楼

这条路径中间有一步可能是-100，后面的给补回来90. 那最开始带10个就不够了

【在 a*********2 的大作中提到】

: 为什么要这个条件？
: 算出最大值是-10，那么最小所需要的能量就是10，以使得在终点处的能量至少为0.

j*u2010-02-17 08:02

22 楼

黄鹂真懒阿
你不在有用的帖子里面创造点流量阿
呵呵

【在 o********o 的大作中提到】

b*e2010-02-17 08:02

23 楼

所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。

【在 x*******i 的大作中提到】

: 这条路径中间有一步可能是-100，后面的给补回来90. 那最开始带10个就不够了

M*82010-02-17 08:02

24 楼

pai

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

x*i2010-02-17 08:02

25 楼

请大侠详细解释一下怎么控制呀

【在 b***e 的大作中提到】

: 所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。

M*82010-02-17 08:02

26 楼

居然赶上了，差点都忘了，咔咔

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

x*i2010-02-17 08:02

27 楼

请教下，这个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)
: )

s*52010-02-17 08:02

28 楼

b*e2010-02-17 08:02

29 楼

f是dp函数的值，表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重，可以是正的或者负的。

【在 x*******i 的大作中提到】

: 请教下，这个f() 和 w() 各自代表什么？

o*o2010-02-17 08:02

30 楼

居然赶上了，都忘了，咔咔

【在 M*********8 的大作中提到】

: 居然赶上了，差点都忘了，咔咔

t*y2010-02-17 08:02

31 楼

我的思路是这样，每一步需要计算两个变量,
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))
}

a*s2010-02-17 08:02

32 楼

re

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

X*42010-02-17 08:02

33 楼

这个好复杂
其实可以优化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)

x*22010-02-17 08:02

34 楼

热
包子

D*T2010-02-17 08:02

35 楼

RE
我觉得这个算法应该是对的。

【在 t*****y 的大作中提到】

y*m2010-02-17 08:02

36 楼

热

g*g2010-02-17 08:02

37 楼

局部最优不表示全局最优
举个例子， A[n-1][m-1]是整个数组最小值（且远小于其他），也是终点
你要想避免这里力量降低最大，你只能前面积蓄足够力量
所以，这个根据g(i,j)贪婪的DP是不行的
不是选g(i,j)小的，而是选 f(i,j) 大的路径

【在 t*****y 的大作中提到】

c*d2010-02-17 08:02

38 楼

re

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

b*e2010-02-17 08:02

39 楼

似乎没有必要这么麻烦，用我前面的那个直接DP就行了。每个点计算当前点到目标的最
小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
况取最小作为当前点的最小能量要求即可。

【在 g*****g 的大作中提到】

: 局部最优不表示全局最优
: 举个例子， A[n-1][m-1]是整个数组最小值（且远小于其他），也是终点
: 你要想避免这里力量降低最大，你只能前面积蓄足够力量
: 所以，这个根据g(i,j)贪婪的DP是不行的
: 不是选g(i,j)小的，而是选 f(i,j) 大的路径

t*r2010-02-17 08:02

40 楼

baozi
Thanks.

【在 c********d 的大作中提到】

: re

D*T2010-02-17 08:02

41 楼

搞了个例子：
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 的大作中提到】

MO2010-02-17 08:02

42 楼

RE

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

g*g2010-02-17 08:02

43 楼

不好意思，之前没仔细看，
似乎目前为止，只有你的是对的。
f(0,0) 为所求

【在 b***e 的大作中提到】

: 似乎没有必要这么麻烦，用我前面的那个直接DP就行了。每个点计算当前点到目标的最
: 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面
: 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
: 况取最小作为当前点的最小能量要求即可。

d*k2010-02-17 08:02

44 楼

排

g*g2010-02-17 08:02

45 楼

我想说的是，最小“左上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

P*e2010-02-17 08:02

46 楼

re

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

D*T2010-02-17 08:02

47 楼

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;if[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;jf[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;ifor (int j=1;jif (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

k*a2010-02-17 08:02

48 楼

RE

【在 y*m 的大作中提到】

: 热

S*A2010-02-17 08:02

49 楼

这个方法我一开始也是用类似思路的，但是我后来发现这个是不能直接用最短路径的
算法的。你的算法只记录当前点到目标的最少能量是不够的。
任何一条指定的路径，其实是有两个属性。一个是最小能量 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 的大作中提到】

d*e2010-02-17 08:02

50 楼

Chi

S*A2010-02-17 08:02

51 楼

补充一下，我的例子是从左上开始搜素。从右下的话要调整一下。

g*n2010-02-17 08:02

52 楼

热

l*62010-02-17 08:02

53 楼

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)
: )

a*n2010-02-17 08:02

54 楼

rerere!~!!!!!!

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

S*A2010-02-17 08:02

55 楼

这个没有考虑累计 strength 我觉得应该是不对的，看我上面的例子。

【在 l******6 的大作中提到】

:
: cool perspective

o*o2010-02-17 08:02

56 楼

re

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

w*s2010-02-17 08:02

57 楼

你这个例子blaze的算法也是正确的。
你所解释的是为什么很多从出发点开始推到目的点的算法是错误的，但是blaze的方法是
从目的地开始倒推回出发点，这个方法比我之前想到的二分答案要简单很多。这题似乎
只能倒推。

【在 S*A 的大作中提到】

: 这个方法我一开始也是用类似思路的，但是我后来发现这个是不能直接用最短路径的
: 算法的。你的算法只记录当前点到目标的最少能量是不够的。
: 任何一条指定的路径，其实是有两个属性。一个是最小能量 M (越小越好），
: 另外一个是累计能量S（越大约好）。这两个是独立的，任何给定的 M，S，
: 我可以构造出一个路径满足这个条件。其实就是第一步是－M，第二步是 M＋ S。
: 现在有两条路径 1， 2 可以同时到达某一点。
: 如果是最短路径，其中一个路径可以完全舍弃，因为只有一个衡量标准就是S。
: 长的完全废掉。这个点只需要记得他的上一个节点就可以了。
: 但是现在加了一维数，如果 M1 < M2, S1 > S2 的情况，路径1 完胜路径2，
: 路径2 可以废除。

j*u2010-02-17 08:02

58 楼

呵呵

【在 o********o 的大作中提到】

:
: 居然赶上了，都忘了，咔咔

S*A2010-02-17 08:02

59 楼

修改：倒退好像是可以的，让我再想想。
－－－－－－－－－－－－－－－－－－－
倒推把我的矩阵转180 度，调整＋－的次序就可以了。
我分析的道理是一样的。关键问题是不能单单用最小能量来合并
路径。

法是

【在 w*******s 的大作中提到】

: 你这个例子blaze的算法也是正确的。
: 你所解释的是为什么很多从出发点开始推到目的点的算法是错误的，但是blaze的方法是
: 从目的地开始倒推回出发点，这个方法比我之前想到的二分答案要简单很多。这题似乎
: 只能倒推。

j*u2010-02-17 08:02

60 楼

S*A2010-02-17 08:02

61 楼

从后面向前找是对的，佩服啊。
从后面累计的体力就没有用了，因为反正到终点剩多少体力
没有关系。只需要最少体力就可以了。
那路径的确可以合并，就是后面向前的最短路径问题。
blaze 的思路很对。我怎么就没有想到呢。

x*i2010-02-17 08:02

62 楼

w*s2010-02-17 08:02

63 楼

看来做题的时候需要不停的变换思路啊

【在 S*A 的大作中提到】

: 从后面向前找是对的，佩服啊。
: 从后面累计的体力就没有用了，因为反正到终点剩多少体力
: 没有关系。只需要最少体力就可以了。
: 那路径的确可以合并，就是后面向前的最短路径问题。
: blaze 的思路很对。我怎么就没有想到呢。

n*h2010-02-17 08:02

64 楼

排

m*k2010-02-17 08:02

65 楼

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)
: )

d*w2010-02-17 08:02

66 楼

吃

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

m*k2010-02-17 08:02

67 楼

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 的值吧。

p*r2010-02-17 08:02

68 楼

PAI

r*c2010-02-17 08:02

69 楼

blaze倒退有简介又对，正面来是不对的
为什么呢，因为求的是从起始点开始所有路径里面min max。新加了一个点在后面的话
，即使你找到了相邻的min max，但是这个点自己是有weight的，而且这个weight在最
后，如果weight很小的话完全可以和以前的min max无关。往回退就不一样了，因为min
max是从第一个点算起的，只要找到零界点就可以了，

b*h2010-02-17 08:02

70 楼

b*e2010-02-17 08:02

71 楼

语体教？

min

【在 r****c 的大作中提到】

: blaze倒退有简介又对，正面来是不对的
: 为什么呢，因为求的是从起始点开始所有路径里面min max。新加了一个点在后面的话
: ，即使你找到了相邻的min max，但是这个点自己是有weight的，而且这个weight在最
: 后，如果weight很小的话完全可以和以前的min max无关。往回退就不一样了，因为min
: max是从第一个点算起的，只要找到零界点就可以了，

s*52010-02-17 08:02

72 楼

Chi

【在 j******u 的大作中提到】

: 大家来吃午餐吧
: 20个
: 呵呵，顺便聊聊天

m*g2010-02-17 08:02

73 楼

靠，百撕不得其姐，而大侠却一枪中的，人与人的差距咋就这么大呢。

【在 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)
: )

l*g2010-02-17 08:02

74 楼

chi

P*H2010-02-17 08:02

75 楼

从终点到起点，反过来DP。一次就够了。

【在 m**********g 的大作中提到】

: 靠，百撕不得其姐，而大侠却一枪中的，人与人的差距咋就这么大呢。

r*h2010-02-17 08:02

76 楼

饿死了:)

m*c2010-02-17 08:02

77 楼

backtrack, 一次DP就搞定了。
这个题目类似于crack the coding interview 8.2 题。

w*n2010-02-17 08:02

78 楼

雨票有么?...

e*32010-02-17 08:02

79 楼

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 HashMapInteger>();

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; ifor (int j=0; jmatrix[i][j] = rand.nextInt(50);
if (rand.nextBoolean()){
matrix[i][j] *= -1;
}
}
}
return matrix;
}

public static void printMatrix(int[][] matrix){
for (int i=0; iint j = 0;
for (; jSystem.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 的大作中提到】

z*q2010-02-17 08:02

80 楼

missed again

A*c2010-02-17 08:02

81 楼

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)
: )

i*n2010-02-17 08:02

82 楼

b*g2010-02-17 08:02

83 楼

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的简单变形。
: 个人觉得这个两行的解法之后没有任何继续讨论的必要了。

c*t2010-02-17 08:02

84 楼

l*a2010-02-17 08:02

85 楼

mark

j*e2010-02-17 08:02

86 楼

晚餐了

f*t2010-02-17 08:02

87 楼

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;

k*y2010-02-17 08:02

88 楼

又来玩鸟，没包子吃，555

a*w2010-02-17 08:02

89 楼

典型dp吧
最简单就是画个一样大矩阵
死了的格不能往下走
如果空间大小是concern,
保留两行就够
或者跟对角线一样长。有点自找麻烦
还是两行比较好

【在 x*******i 的大作中提到】

k*y2010-02-17 08:02

90 楼

又来玩鸟，没包子吃，555

a*w2010-02-17 08:02

91 楼

哦看错题了
那就从右下往左上走
保留每格最小值？
F(I,j)=min(下，右）- strength(I,j)
小于0清0。

【在 a******w 的大作中提到】

: 典型dp吧
: 最简单就是画个一样大矩阵
: 死了的格不能往下走
: 如果空间大小是concern,
: 保留两行就够
: 或者跟对角线一样长。有点自找麻烦
: 还是两行比较好

k*y2010-02-17 08:02

92 楼

又来玩鸟，没包子吃，555

c*w2010-02-17 08:02

93 楼

DP seems not work because history dependent path, use variation of Dijkstra
(similar to bottleneck shortest path)

【在 x*******i 的大作中提到】

M*o2010-02-17 08:02

94 楼

蛋定！没包子吃也不用唠叨三遍呀。。。哈哈

【在 k*****y 的大作中提到】

: 又来玩鸟，没包子吃，555

t*y2010-02-17 08:02

95 楼

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)
?

k*y2010-02-17 08:02

96 楼

哈哈，没想发三遍啊，点一下没动静，就点点点，结果就有回声效果了，嘿嘿

【在 M****o 的大作中提到】

: 蛋定！没包子吃也不用唠叨三遍呀。。。哈哈

s*52010-02-17 08:02

97 楼

这个解法有问题。任何路径如果出现非正元素即作废，所以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)
: )

M*82010-02-17 08:02

98 楼

包子没吃到，3毛伪币都不让人挣呀

【在 M****o 的大作中提到】

: 蛋定！没包子吃也不用唠叨三遍呀。。。哈哈

P*i2010-02-17 08:02

99 楼

blaze的是正解

【在 g*****g 的大作中提到】

: 不好意思，之前没仔细看，
: 似乎目前为止，只有你的是对的。
: f(0,0) 为所求

w*d2010-02-17 08:02

100 楼

baozi

S*s2010-02-17 08:02

101 楼

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());
}
}

M*o2010-02-17 08:02

102 楼

我是xmjdh呀
我不但没吃到包子，连3毛伪币都没挣到呀

【在 M*********8 的大作中提到】

: 包子没吃到，3毛伪币都不让人挣呀

l*02010-02-17 08:02

103 楼

这个就是求“路径和”最大值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;

k*y2010-02-17 08:02

104 楼

⊙﹏⊙b汗，提醒我还吃到了0.03个包子哈，不过还不够塞牙缝的呀，呵呵

【在 M****o 的大作中提到】

: 我是xmjdh呀
: 我不但没吃到包子，连3毛伪币都没挣到呀