执行N >= 10^7的代码时出现分段故障(核心转储)错误

Question

我正在尝试为codeChef的problem Bytelandian gold coins写一段代码。该代码适用于n < 10^7，但对于较高的值会产生分割错误。我找过datatypes which could hold bigger numbers，但也没找到。我当然认为我的代码中没有问题，但可能递归树变得太大，编译器无法处理。这是代码。

#include <bits/stdc++.h>

using namespace std;

#define lli long long int

lli divide(lli n, lli dp[])
{
    lli ans = 0;

    if (n == 0)
        return 0;

    if (dp[n] != 0)
        return dp[n];

    lli m1 = floor(divide(n / 2, dp));
    lli m2 = floor(divide(n / 3, dp));
    lli m3 = floor(divide(n / 4, dp));
    lli sum = m1 + m2 + m3;
    ans = max(sum, n);
    dp[n] = ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        lli n;
        cin >> n;
        lli dp[n + 1] = { 0 };
        lli ans = divide(n, dp);
        cout << ans << endl;
    }
}

Answer 1

我认为在这一行中，堆栈上分配了一个大数组：

lli dp[n + 1] = {0};

这很可能是段错误的原因。您可能希望将其更改为std::vector。例如：

std::vector<lli> dp(n + 1, 0);

或者，您可以将其设置为静态的，或者使用new[]分配它(可能对所有测试只分配一次，以最小化开销，在这种情况下，您需要记住使用delete[]正确地清理它)。

Answer 2

正如@sbarzowski所提到的，当您这样做时

lli dp[n+1] = {0}

您正在请求堆栈上的内存分配。虽然在堆栈上分配内存会导致更快的访问时间，但会导致内存不足。相反，应该在堆上使用内存分配。为此，您可以使用new操作符。有关堆栈与堆分配的详细说明，请查看：https://www.geeksforgeeks.org/stack-vs-heap-memory-allocation/

此外，在处理要存储在一起的大量元素时，建议使用std::vector或std::array。参考资料：Vector vs Array for large number of elements?