e*******8
发帖数: 94 | | f******p
发帖数: 173 | 2 我怎么觉得是O(n^3)呢
http://stackoverflow.com/questions/12278528/find-subset-with-el
里面ElKamina的答案是对的，不过有一处没说清楚,X[i,j] 应该是 the optimum
result of selecting j elements from the first i elements provided that A[j-1
] is included.
贴个代码
public int cal(int[] a, int k)
{
if (k <2 || a == null ||a.length < 2)
return -1;
Arrays.sort(a);
if (k == 2)
return a[a.length-1] -a[0];
int[][] res = new int[a.length + 1][a.length +1];
for (int i = 2; i < res.length; i++)
{
res[i][2] = a[i-1] -a[0];
}
for(int j = 3; j < res.length; j++)
{
for(int i = j; i
{
int max = Integer.MIN_VALUE;
for (int l = j-1; l
{
int r = Math.min(res[l][j-1], a[i-1]-a[l-1]);
if (r > max)
max = r;
}
res[i][j] = max;
}
}
int max = Integer.MIN_VALUE;
for(int i = k; i
{
if (res[i][k] > max)
max = res[i][k];
}
return max;
}
【在 e*******8 的大作中提到】
: 题目在此:
: http://stackoverflow.com/questions/12278528/find-subset-with-el
: 解法：
: http://algnotes.wordpress.com/2012/09/20/find-subset-with-eleme
: 没想明白照什么顺序解决O(nk)个subproblems才能有O(nk)的时间复杂度？
| e*******8
发帖数: 94 | 3 ElKamina的答案是写的有点不清楚：X[i][j], 我看他的那个表，意思好象是optimum
cost to select j furthest points from {p_1, ..., p_i}, ending at p_i. 所以i
的范围是[2,n]， j的范围是[2,k]. (The cost of a set of points is defined
as the minimum pairwise distance between the points in the set).
所以dp要填的entries有O(nk)个. 我想的实现方法，和你贴的代码差不多，所以最后时
间复杂度是O(n^2 k).
但是又考虑有的dp问题，虽然要填的table也很大，但是有比较快的填法（比如longest
arithmetic progression, 那里table大小是O(n^2), 每个entry用第归公式一个一个
算，也要O(n^3), 但是有比较聪明的方法可以在O(n^2)的时间内填完)....
这个题么，现在我只想出来j＝３的行，O(n)个entry可以在O(n)时间内全部算出来.因
为起始点是p_１，结束点是p_i，所以随着p_i向右移动，中间的那个点也应该是单向右
移动的。但是j ＞＝４的，就好象没这么简单了。 |
|
