何为分配比数组所需空间更多的空间的意义

Question

在竞赛编程中，经常有人建议我为零维以上的数据类型（即数组或数组数组）分配比任务限制实际要求更多的空间。

例如，对于在从上到下的整数值三角形中选择最大高度为100的路径时计算最大值和的简单DP任务（见下面的示例），建议我为110行分配空间。

我得到的理由是：万一它需要更多的空间，它就不会坠毁。

然而，我看不出这背后的逻辑。如果一个程序试图使用这个数组的更多空间，至少在我看来，它必须包含一些错误。在这种情况下，分配更多的空间会更有意义而不是，因此会注意到错误，而不是给程序空间去做它不应该做的事情。

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

---

上述任务的示例（右下角）：

没有额外分配： nbsp nbsp nbsp nbsp nbsp nbsp nbsp 附加分配：

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;
}

Answer 1

给你的答案是完全合法的。

我的简短回答是：这只是一种面向未来的技术。安全总比抱歉好。此外，现在存储并不是一个问题。在软盘时代，这可能是一个更大的问题。

在我看来，如果我能让我的代码为未来做好准备，并且不太可能以允许它在零的行和列上浪费几千字节为代价而崩溃，那就顺其自然吧。这是一个很小的应急代价。：）

Answer 2

如果您考虑了Fail-Fast开发策略，那么您是对的。