g***m
发帖数: 85 | 1 在leetcode上做了几道DP的题目，用的是很标准的二维数组。judge small都过了，
judge large的时候说memory limit exceed。（用动态数组，如果用静态，显示
runtime error）。试着把数组砍掉一半变成三角形，还是超。
有什么好办法么？可以想到的是，动态数组一边算一边删不用的空间，但code很难写啊
，几乎肯定得出错... |
i**********e
发帖数: 1145 | 2 是哪一道题呢？
我帮你看看吧。
你可以 return 空答案，然后看 large input 的testcase最大size，然后 allocate
那个size应该就好了。
面试时不用 dynamic alloc，assume input 不会超过这个size就好了。 |
g***m
发帖数: 85 | 3 Jump game II 和 Largest Rectangle in Histogram。
我可以看到fail的test case，就是一个size特别大的数组（里面的元素并不大）。我
就是根据input数组长度定义二维数组的，（三角形，砍了一半已经）
int **res;
res = new int *[n+1];
for (int i = 0; i < n; i++)
res[i] = new int[n+1-i];
剩下的为空，都是memory limit exceed。
这个input size感觉是分配n的空间不会超过，n^2就不行了。
【在 i**********e 的大作中提到】
: 是哪一道题呢？
: 我帮你看看吧。
: 你可以 return 空答案，然后看 large input 的testcase最大size，然后 allocate
: 那个size应该就好了。
: 面试时不用 dynamic alloc，assume input 不会超过这个size就好了。
|
l*********8
发帖数: 4642 | 4 Jump game II 不需要二维数组吧。
【在 g***m 的大作中提到】
: Jump game II 和 Largest Rectangle in Histogram。
: 我可以看到fail的test case，就是一个size特别大的数组（里面的元素并不大）。我
: 就是根据input数组长度定义二维数组的，（三角形，砍了一半已经）
: int **res;
: res = new int *[n+1];
: for (int i = 0; i < n; i++)
: res[i] = new int[n+1-i];
: 剩下的为空，都是memory limit exceed。
: 这个input size感觉是分配n的空间不会超过，n^2就不行了。
|
i**********e
发帖数: 1145 | 5 对，因为 n 最大可以大到 25000.n^2 空间肯定不行。
【在 g***m 的大作中提到】
: Jump game II 和 Largest Rectangle in Histogram。
: 我可以看到fail的test case，就是一个size特别大的数组（里面的元素并不大）。我
: 就是根据input数组长度定义二维数组的，（三角形，砍了一半已经）
: int **res;
: res = new int *[n+1];
: for (int i = 0; i < n; i++)
: res[i] = new int[n+1-i];
: 剩下的为空，都是memory limit exceed。
: 这个input size感觉是分配n的空间不会超过，n^2就不行了。
|
g***m
发帖数: 85 | 6 hmm...
所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。
【在 i**********e 的大作中提到】
: 对，因为 n 最大可以大到 25000.n^2 空间肯定不行。
|
l*********8
发帖数: 4642 | 7 这道题目是求图上两点间最近距离的特例，可以用Dijkstra算法的简化版.
【在 g***m 的大作中提到】
: hmm...
: 所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。
|
i**********e
发帖数: 1145 | 8 jump game 可以用 greedy，可以考古本版，火鸡给过很好的解法。
histogram 那题用 cache 来做的方法需要 O(n^2) 空间，过不了large testcase。
large testcase需要最优解法，可以参考网上给的 stack 解答。
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm
【在 g***m 的大作中提到】
: hmm...
: 所以有什么办法能把DP的空间降到n^2以下呢？除了一边算一边动态释放空间。
|
h****e
发帖数: 928 | 9 一般Memory limit exceeded或者Runtime limit exceeded
就说明算法不够有效，要另外考虑。实在想不出来了就放狗吧。 |
