Redian新闻
>
A Primer on Valuation Models
avatar
A Primer on Valuation Models# Stock
x*i
1
假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有
正数也有负数,遇到正数表示你的strength增加那么多,遇到负数表示strength减少那
么多,在任何时刻如果你的strength小于等于0,那么你就挂了。在一开始你有一定的
初始的strength,现在问这个初始的strength最少是多少,才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
直接贪婪做法肯定不行的。
avatar
j*u
2
大家来吃午餐吧
20个
呵呵,顺便聊聊天
avatar
l*r
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
avatar
a*2
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最少是多少,才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。

avatar
h*u
5
竟然在出门前赶上了。哈哈

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
e*n
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

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

★ 发自iPhone App: ChineseWeb 7.8

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

avatar
o*o
8


【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
P*r
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).

avatar
e*b
10
吃!
avatar
c*7
11
大概想了下,感觉DP的话每个格要保留的数据需要挺多才能不丢失信息。
设第一格为零,第一格开始做DP,每个格保留一个list,list里每个元素为某条路径的
当前体力值和路径最小体力值,list按照路径最小体力值排序。计算某一格新的list的
时候,merge左边格子和上面格子的两个list,去掉路径最小体力值小且当前体力值小的
元素。
到最后一格的时候找到当前体力值大于等于零且[路径最小体力值]的最小值
avatar
b*0
12
ha
pai
avatar
y*u
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]);
avatar
t*g
14
pai 包子.
avatar
b*e
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 的大作中提到】
: 假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有
: 正数也有负数,遇到正数表示你的strength增加那么多,遇到负数表示strength减少那
: 么多,在任何时刻如果你的strength小于等于0,那么你就挂了。在一开始你有一定的
: 初始的strength,现在问这个初始的strength最少是多少,才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。

avatar
j*u
16
呵呵,不敬业,我是赶回来的
看看我的小白鼠的报告

【在 h*********u 的大作中提到】
: 竟然在出门前赶上了。哈哈
avatar
g*g
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]);

avatar
e*a
18
同吃!
avatar
a*2
19
为什么要这个条件?
算出最大值是-10,那么最小所需要的能量就是10,以使得在终点处的能量至少为0.

【在 P*******r 的大作中提到】
: 缺了当中每一步都大于0的条件
avatar
a*n
20
re

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

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

【在 a*********2 的大作中提到】
: 为什么要这个条件?
: 算出最大值是-10,那么最小所需要的能量就是10,以使得在终点处的能量至少为0.

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

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

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

【在 x*******i 的大作中提到】
: 这条路径中间有一步可能是-100,后面的给补回来90. 那最开始带10个就不够了
avatar
M*8
24
pai

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
x*i
25
请大侠详细解释一下怎么控制呀

【在 b***e 的大作中提到】
: 所以只要dp的时候控制不要小于0即可。这个和经典的求最优路径的题目区别不大。
avatar
M*8
26
居然赶上了,差点都忘了,咔咔

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
x*i
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)
: )

avatar
s*5
28
re
avatar
b*e
29
f是dp函数的值,表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重,可以是正的或者负的。

【在 x*******i 的大作中提到】
: 请教下, 这个f() 和 w() 各自代表什么?
avatar
o*o
30

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

【在 M*********8 的大作中提到】
: 居然赶上了,差点都忘了,咔咔
avatar
t*y
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))
}
avatar
a*s
32
re

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
X*4
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)

avatar
x*2
34

包子
avatar
D*T
35
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)

avatar
y*m
36
avatar
g*g
37
局部最优不表示全局最优
举个例子, 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)

avatar
c*d
38
re

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

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

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

avatar
t*r
40
baozi
Thanks.

【在 c********d 的大作中提到】
: re
avatar
D*T
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 的大作中提到】
: 局部最优不表示全局最优
: 举个例子, A[n-1][m-1]是整个数组最小值(且远小于其他),也是终点
: 你要想避免这里力量降低最大,你只能前面积蓄足够力量
: 所以,这个根据g(i,j)贪婪的DP是不行的
: 不是选g(i,j)小的,而是选 f(i,j) 大的路径

avatar
MO
42
RE

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

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

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

avatar
d*k
44
avatar
g*g
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

avatar
P*e
46
re

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
D*T
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

avatar
k*a
48
RE

【在 y*m 的大作中提到】
: 热
avatar
S*A
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 的大作中提到】
: 似乎没有必要这么麻烦,用我前面的那个直接DP就行了。每个点计算当前点到目标的最
: 小能量要求。当前点只能走到下面或右面的点。如果走下面的点,那么最小要求是下面
: 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情
: 况取最小作为当前点的最小能量要求即可。

avatar
d*e
50
Chi
avatar
S*A
51
补充一下,我的例子是从左上开始搜素。从右下的话要调整一下。
avatar
g*n
52
avatar
l*6
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)
: )

avatar
a*n
54
rerere!~!!!!!!

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
S*A
55
这个没有考虑累计 strength 我觉得应该是不对的,看我上面的例子。

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

avatar
o*o
56
re

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

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

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

avatar
j*u
58
呵呵

【在 o********o 的大作中提到】
:
: 居然赶上了,都忘了,咔咔

avatar
S*A
59
修改: 倒退好像是可以的,让我再想想。
-------------------
倒推把我的矩阵转180 度,调整 +- 的次序就可以了。
我分析的道理是一样的。关键问题是不能单单用最小能量来合并
路径。

法是

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

avatar
j*u
60
re
avatar
S*A
61
从后面向前找是对的,佩服啊。
从后面累计的体力就没有用了,因为反正到终点剩多少体力
没有关系。只需要最少体力就可以了。
那路径的确可以合并,就是后面向前的最短路径问题。
blaze 的思路很对。我怎么就没有想到呢。
avatar
x*i
62
re
avatar
w*s
63
看来做题的时候需要不停的变换思路啊

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

avatar
n*h
64
avatar
m*k
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)
: )

avatar
d*w
66


【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
m*k
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 的值吧。

avatar
p*r
68
PAI
avatar
r*c
69
blaze倒退有简介又对,正面来是不对的
为什么呢,因为求的是从起始点开始所有路径里面min max。新加了一个点在后面的话
,即使你找到了相邻的min max,但是这个点自己是有weight的,而且这个weight在最
后,如果weight很小的话完全可以和以前的min max无关。往回退就不一样了,因为min
max是从第一个点算起的,只要找到零界点就可以了,
avatar
b*h
70
re
avatar
b*e
71
语体教?

min

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

avatar
s*5
72
Chi

【在 j******u 的大作中提到】
: 大家来吃午餐吧
: 20个
: 呵呵,顺便聊聊天

avatar
m*g
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)
: )

avatar
l*g
74
chi
avatar
P*H
75
从终点到起点,反过来DP。一次就够了。

【在 m**********g 的大作中提到】
: 靠,百撕不得其姐, 而大侠却一枪中的, 人与人的差距咋就这么大呢。
avatar
r*h
76
饿死了:)
avatar
m*c
77
backtrack, 一次DP就搞定了。
这个题目类似于crack the coding interview 8.2 题。
avatar
w*n
78
雨票有么?...
avatar
e*3
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 的大作中提到】
: 假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有
: 正数也有负数,遇到正数表示你的strength增加那么多,遇到负数表示strength减少那
: 么多,在任何时刻如果你的strength小于等于0,那么你就挂了。在一开始你有一定的
: 初始的strength,现在问这个初始的strength最少是多少,才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。

avatar
z*q
80
missed again
avatar
A*c
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)
: )

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

avatar
c*t
84
re
avatar
l*a
85
mark
avatar
j*e
86
晚餐了
avatar
f*t
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;
avatar
k*y
88
又来玩鸟,没包子吃,555
avatar
a*w
89
典型dp吧
最简单就是画个一样大矩阵
死了的格不能往下走
如果空间大小是concern,
保留两行就够
或者跟对角线一样长。有点自找麻烦
还是两行比较好

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

avatar
k*y
90
又来玩鸟,没包子吃,555
avatar
a*w
91
哦看错题了
那就从右下往左上走
保留每格最小值?
F(I,j)=min(下,右)- strength(I,j)
小于0清0。

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

avatar
k*y
92
又来玩鸟,没包子吃,555
avatar
c*w
93
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最少是多少,才能保证你能够找到一条路
: 走到右下角。每一步只能向右或者向下。
: 直接贪婪做法肯定不行的。

avatar
M*o
94
蛋定!没包子吃也不用唠叨三遍呀。。。哈哈

【在 k*****y 的大作中提到】
: 又来玩鸟,没包子吃,555
avatar
t*y
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)
?
avatar
k*y
96
哈哈,没想发三遍啊,点一下没动静,就点点点,结果就有回声效果了,嘿嘿

【在 M****o 的大作中提到】
: 蛋定!没包子吃也不用唠叨三遍呀。。。哈哈
avatar
s*5
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)
: )

avatar
M*8
98
包子没吃到,3毛伪币都不让人挣呀

【在 M****o 的大作中提到】
: 蛋定!没包子吃也不用唠叨三遍呀。。。哈哈
avatar
P*i
99
blaze的是正解

【在 g*****g 的大作中提到】
: 不好意思,之前没仔细看,
: 似乎目前为止,只有你的是对的。
: f(0,0) 为所求

avatar
w*d
100
baozi
avatar
S*s
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());
}
}
avatar
M*o
102
我是xmjdh呀
我不但没吃到包子,连3毛伪币都没挣到呀

【在 M*********8 的大作中提到】
: 包子没吃到,3毛伪币都不让人挣呀
avatar
l*0
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;
avatar
k*y
104
⊙﹏⊙b汗,提醒我还吃到了0.03个包子哈,不过还不够塞牙缝的呀,呵呵

【在 M****o 的大作中提到】
: 我是xmjdh呀
: 我不但没吃到包子,连3毛伪币都没挣到呀

avatar
x*6
105
re
avatar
x*2
106
avatar
s*r
107
每次我都赶不上
有娃的人,周末忙啊
avatar
T*y
108
Re~
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。