分配比数组所需更多 space 的意义在哪里

Question

在竞赛编程中，我经常被建议为大于零维的数据类型（即数组或数组的数组）分配比实际要求更多的 space任务。

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

给出我的原因：万一它需要更多 space，它不会崩溃。

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

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

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

无额外分配：有额外分配：

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 开发策略，你是对的。

分配比数组所需更多 space 的意义在哪里

Where is the sense in allocating more space than required for an array

arrays

allocation