如何避免以下代码的 SEGMENTATION ERROR？

Question

我收到以下代码的分段错误。这是 the SPOJ problem "Coins".

的解决方案

我经历了 How to avoid SIGSEGV? 并确保不使用未初始化的指针，不访问内存不足等（给定 n ≤ 10⁹).

我知道数组a[1000000000]会导致栈溢出，所以我用了std::map。 std::map 会导致堆栈溢出吗？我的代码有什么问题？

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

map<unsigned long long int, unsigned long long int> a;

unsigned long long int dp(unsigned long long int n)
{   
   if (a.find(n) == a.end())
      a[n] = dp(n/2) + dp(n/3) + dp(n/4);

   return a[n];
}

int main()
{
    for (unsigned long long int i = 1; i <= 24; i++) {
        a[i] = i;
        if (i == 12 || i == 24)
           a[i] = i + 1;
    }

    unsigned long long int n = 0;
    cin >> n;

    while (!feof(stdin)) {
        printf("%llu\n", dp(n));
        cin >> n;
    }
}

Answer 1

您在 dp(0) 通话中收到 SIGSEGV。它会导致无限递归。

顺便说一句，你的答案是错误的，例如 24 的答案不是 25。尽量避免魔术常数，设置 a[0] = 0 就足够了，并且更准确 dp 函数：

uint32_t dp(uint32_t n) {
    if (a.find(n) == a.end())
        a[n] = max(n, dp(n / 2) + dp(n / 3) + dp(n / 4));

    return a[n];
}

从上面可以看出，32位类型足以存储任何可能的答案。

如何避免以下代码的 SEGMENTATION ERROR？

How to avoid SEGMENTATION ERROR for the code below?

c++

maps

dynamic-programming

segmentation-fault