o*****e
发帖数: 99 | 1 问一题
一个矩阵
左到右单增
上到下单增
找左上到右下最大和路径
要求O(n)
DP algorithm O(n2), I cannot find the answer of O(n).
Any ideas? | B********8
发帖数: 9 | 2 Greedy from TopLeft to BottomRight? | h*********n
发帖数: 11319 | 3 1 2 3
100 101 199
102 103 200
【在 B********8 的大作中提到】
: Greedy from TopLeft to BottomRight?
| B********8
发帖数: 9 | 4 You are right. Looking forward to seeing a O(N) solution (is LZ sure about
it?) | o*****e
发帖数: 99 | 5 yes, m*n matrix
原题目需要 O(m+n) | l*********8
发帖数: 4642 | 6 题目是不是有问题？
矩阵是不是两个sorted arrays 的和？
a0+b0 a0+b1 ... a0+bm
a1+b0 a1+b1 .....a1+bm
....
an+b0 an+b1 ... an+bm
如果是这样的矩阵的话，就用greedy方法， O(n+m)
楼主的题目感觉不太可能有O(n)解法。
【在 o*****e 的大作中提到】
: 问一题
: 一个矩阵
: 左到右单增
: 上到下单增
: 找左上到右下最大和路径
: 要求O(n)
: DP algorithm O(n2), I cannot find the answer of O(n).
: Any ideas?
| g**********y
发帖数: 14569 | 7 很怀疑有O(n)的解，网上讨论这个题的，有一个很好的质疑：O(n)就意味着你不能扫描所有的点。但是矩阵里的任何一个点，好象都可以设计成最佳路径的必过点。
换个角度说，对n^2个元素的matrix, O(n)的解必然是局部最优就导致全局最优的，只能是greedy, 或者greedy的变种。 | d*******l
发帖数: 338 | 8 同意，昨天想了半天，觉得无法从本质上排除任何一条可能的路径。如果不加别的限制
条件，那O(n)的方法应该无法消除所有的不确定性，结果就是不能保证正确性
描所有的点。但是矩阵里的任何一个点，好象都可以设计成最佳路径的必过点。
只能是greedy, 或者greedy的变种。
【在 g**********y 的大作中提到】
: 很怀疑有O(n)的解，网上讨论这个题的，有一个很好的质疑：O(n)就意味着你不能扫描所有的点。但是矩阵里的任何一个点，好象都可以设计成最佳路径的必过点。
: 换个角度说，对n^2个元素的matrix, O(n)的解必然是局部最优就导致全局最优的，只能是greedy, 或者greedy的变种。
| l***i
发帖数: 1309 | 9 Let the matrix be a[m,n], the problem asks for best(m,n)
best(i,j) = a[i,j] + max { \sum_c=1^j a[1,c] + \sum_r=1^i a[r,j],
\sum_r=1^i a[r,1] + \sum_c=1^j a[i,c],
best(i-1,j-1) + a[i-1,j]
best(i-1,j-1) + a[i,j-1]
The two sums can be computed in O(1) time by prefix sum. Each step both i
and j decrease by 1. So it is O(m+n) time. Note that the matrix a[m,n] does
not have to be Young's matrix. No ordering on row or column is needed. | d*******l
发帖数: 338 | 10 能保证正确性吗？除了上下两条路以及best(i-1,j-1)，剩下的情况怎么排除？
有可能先在中间走一段，然后就走到某个边上一直贴边走，这个不属于上述情况的任何
一种，能否证明这一定不可能是最优的？
does
【在 l***i 的大作中提到】
: Let the matrix be a[m,n], the problem asks for best(m,n)
: best(i,j) = a[i,j] + max { \sum_c=1^j a[1,c] + \sum_r=1^i a[r,j],
: \sum_r=1^i a[r,1] + \sum_c=1^j a[i,c],
: best(i-1,j-1) + a[i-1,j]
: best(i-1,j-1) + a[i,j-1]
: The two sums can be computed in O(1) time by prefix sum. Each step both i
: and j decrease by 1. So it is O(m+n) time. Note that the matrix a[m,n] does
: not have to be Young's matrix. No ordering on row or column is needed.
| l***i
发帖数: 1309 | 11 I think you can prove by induction on m,n.
The only path not covered by best(m-1,n-1) is the two paths appearing as the
first two sums in the max. | g**********y
发帖数: 14569 | 12 反例：
1 2 3 4
2 100 102 103
3 101 103 104
4 200 201 202
best(2,2) = 1 + 2 + 100 + 102 + 103
best(3,3) = 1 + 2 + 100 + 101 + 200 + 201 + 202 | d*******l
发帖数: 338 | 13 应该不能，我上面提到的先在中间走一段，然后贴边走的就不属于其中的任何一种
the
【在 l***i 的大作中提到】
: I think you can prove by induction on m,n.
: The only path not covered by best(m-1,n-1) is the two paths appearing as the
: first two sums in the max.
|
|
