分配空间大于数组所需空间的意义

在比赛编程中，我经常被建议分配更多的空间，而不是超过零维数据类型所需的空间，例如数组或数组数组，比任务限制实际需要的要多。分配空间大于数组所需空间的意义

E.g.对于从顶部到底部以整数值三角形选择路径时计算最大值总和的最简单DP任务（最大高度为100）（请参见下面的示例），建议我为110行分配空间。

我给出的理由：以防万一它需要更多的空间，它不会崩溃。

但是，我没有看到这背后的逻辑。如果一个程序试图使用这个数组的更多空间，至少在我看来，它必须包含一些错误。在这种情况下，不是可以分配更多的空间，所以这个bug会被注意到，而不是让程序有空间去做任何它不应该做的事情。

所以我希望有人能给我一个解释，说明为什么这样做，在哪些情况下，这实际上是有用的。

实施例为上述任务（右下角）：

如果没有额外的分配：随着额外分配：

1 0 0 0         1 0 0 0 0 0 
2 3 0 0         2 3 0 0 0 0 
4 5 6 0         4 5 6 0 0 0 
7 8 9 5         7 6 9 5 0 0 
             0 0 0 0 0 0 
             0 0 0 0 0 0 
             0 0 0 0 0 0

在这个例子中，最大的路径。总和将是右右左为1 + 3 + 6 + 9 = 19

一个例子C++实现的总和来解决问题（完美地工作而无需额外分配）：

#include <iostream> 
#include <vector> 

using namespace std; 

vector<vector<int>> p(100, vector<int>(100)); 
vector<vector<int>> dp(100, vector<int>(100, -1)); 
int n = 0; 

int maxsum(int r, int c) { 
    if (r == n-1) { 
     dp[r][c] = p[r][c]; 
    } else { 
     if (dp[r][c] == -1) { 
      dp[r][c] = max(maxsum(r+1, c), maxsum(r+1, c+1)) + p[r][c]; 
     } 
    } 
    return dp[r][c]; 
} 

int main() { 
    cin >> n; 
    for (int i = 0; i < n; ++i) { 
     for (int j = 0; j <= i; j++) { 
      cin >> p[i][j]; 
     } 
    } 
    cout << maxsum(0, 0) << "\n"; 
    return 0; 
}

来源

2015-04-06 s3lph

只是想知道你能给它的链接它说的是这样吗？ – WannaBeCoder 2015-04-06 11:54:19

通过分配更多的“空间”比你需要的不是保护软件免受错误。你正在让自己的生活变得更轻松，就好像在后一天你需要使用一些额外的行/列，你不需要重新定义数组。 – 2015-04-06 11:59:08

@WannaBeCoder“在比赛编程中，我经常被推荐”......口头表达。 – s3lph 2015-04-06 15:54:28

答案你被赋予是完全合法的。

我的简答：这只是一种面向未来的技术。比对不起更安全。此外，现在不像存储是一个问题。在软盘的日子里，这可能是更多的问题。

我看到它的方式，如果我可以让我的代码更具备未来就绪性，并且不太可能以允许它在行和零列上浪费几千字节为代价而崩溃，那就这样吧。这是支付应急费用的小代价。 :)

来源

2015-04-06 11:55:01 Tim

如果您考虑失败快速发展的策略，那么您是对的。

来源

2015-04-06 17:39:28 Dragonborn

分配空间大于数组所需空间的意义

回答

相关问题