r***8
发帖数: 86 | 1 两海盗在分金币，金币放在N个瓶子里， 每个瓶子放有金币，瓶子放在一排，两海盗
都知道每个瓶子放的金币数目，分的规则是这样的，每个海盗呢只也取边上的一个瓶子
，第一个，或最后一个。
请你写一算法，帮其中一海盗获得最可以多的金币，前提是两海盗可是一样的聪明啊。
给出算法复杂度，能用O（N*N）写出吗？ | x*****p
发帖数: 1707 | 2 Using recursive.
Suppose an array A of integers is given to hold all golden pieces. Its index
is from 0 to N-1.
Let function f(int startIndex, int endIndex) returns the maximum money you
can get.
int f(A, int startIndex, int endIndex) {
int sum = summation from A[startIndex] to A[endIndex];
if (startIndex==endIndex) return A[startIndex];
int choice1 = sum - f(A, startIndex+1, endIndex);
int choice2 = sum - f(A, startIndex, endIndex-1);
return (choice1>choice2?choice1:choice2)
}
run f(A, 0, N-1) | r**u
发帖数: 1567 | 3 DP, 最近讨论过,考古一下.
【在 r***8 的大作中提到】
: 两海盗在分金币，金币放在N个瓶子里， 每个瓶子放有金币，瓶子放在一排，两海盗
: 都知道每个瓶子放的金币数目，分的规则是这样的，每个海盗呢只也取边上的一个瓶子
: ，第一个，或最后一个。
: 请你写一算法，帮其中一海盗获得最可以多的金币，前提是两海盗可是一样的聪明啊。
: 给出算法复杂度，能用O（N*N）写出吗？
|
|
