k*j
发帖数: 153 | 1 网上找来的题目
You are given a pyramid; the numbers for example is 2 on the first level, 3
-1 on the second level, 4 7 8 on the third, etc. How do you calculate the
maximum sub sequence of any path traversing the pyramid?
应该是用DP，目前只能想到O(k^2)的做法,k是level数。有没有比这个更快的做法，多
谢！ |
k*j
发帖数: 153 | 2 这题好像G也出过，麻烦大家看看
3
【在 k*j 的大作中提到】
: 网上找来的题目
: You are given a pyramid; the numbers for example is 2 on the first level, 3
: -1 on the second level, 4 7 8 on the third, etc. How do you calculate the
: maximum sub sequence of any path traversing the pyramid?
: 应该是用DP，目前只能想到O(k^2)的做法,k是level数。有没有比这个更快的做法，多
: 谢！
|
S**I
发帖数: 15689 | 3 BFS
3
【在 k*j 的大作中提到】
: 网上找来的题目
: You are given a pyramid; the numbers for example is 2 on the first level, 3
: -1 on the second level, 4 7 8 on the third, etc. How do you calculate the
: maximum sub sequence of any path traversing the pyramid?
: 应该是用DP，目前只能想到O(k^2)的做法,k是level数。有没有比这个更快的做法，多
: 谢！
|
r*******g
发帖数: 1335 | 4 http://www.mitbbs.com/article/JobHunting/31942529_3.html
3
【在 k*j 的大作中提到】
: 网上找来的题目
: You are given a pyramid; the numbers for example is 2 on the first level, 3
: -1 on the second level, 4 7 8 on the third, etc. How do you calculate the
: maximum sub sequence of any path traversing the pyramid?
: 应该是用DP，目前只能想到O(k^2)的做法,k是level数。有没有比这个更快的做法，多
: 谢！
|
k*j
发帖数: 153 | |
e****i
发帖数: 393 | 6 Don't think this is a DP problem. Look into the optimal substructure
carefully. |
l***i
发帖数: 1309 | 7 This is a DP problem and a linear time solution exists, assuming you can use
a linear size space. Since you have O(k^2) numbers, using O(k^2) time seems
acceptable. |
j********x
发帖数: 2330 | 8 I dont think it is possible to have a algorithm linear to (k) (without pre-
processing)
use
seems
【在 l***i 的大作中提到】
: This is a DP problem and a linear time solution exists, assuming you can use
: a linear size space. Since you have O(k^2) numbers, using O(k^2) time seems
: acceptable.
|
D*******e
发帖数: 151 | 9 Compute in a bottom-up manner. For each element x, update it's sum by sum(x)
= x + max{sum(neighbor( x ))};
I think it's linear with the number of elements in the pyramid. |
j********x
发帖数: 2330 | 10 It's k^2 elements un the tree |
c******o
发帖数: 534 | |
