c++ - SPOJ 简单动态规划中的 SIGSEGV 错误

Question

我刚刚开始学习动态规划，我刚刚在 Spoj 上尝试了一个基于 DP 的简单问题。链接 - http://www.spoj.com/problems/MST1/

这是问题陈述 -

On a positive integer, you can perform any one of the following 3 steps.

1.) Subtract 1 from it. ( n = n - 1 )

2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 )

3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 )

Given a positive integer n and you task is find the minimum number of steps that takes n to one.

Input:

The input contains an integer T (1 ≤ T ≤ 100) number of test cases. Second line input is N (0 < N ≤ 2*10^7 ) that indicates the positive number.

Output:

For each case, print the case number and minimum steps.

这是我的代码-

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

// Memo Function returns the smallest number of steps possible for integer a

int memo(int a, int mem[]);

int mem[20000010];

int main() {
    int t;
    scanf("%i", &t);
    for(int i = 1; i <= t; i++) {
        int n;
        scanf("%i", &n);
        memset(mem, -1, sizeof(mem));
        mem[1] = 0;
        printf("Case %i: %i\n", i, memo(n, mem));   
    }
    return 0;
}

int memo(int a, int mem[]) {
    if (mem[a] != -1) return mem[a]; // If the value of smallest steps have already been calculated
    int r; // Current Lowest number of steps
    r = memo(a - 1, mem) + 1;
    if (a % 2 == 0) r = min(r, memo(a/2, mem) + 1);
    if (a % 3 == 0) r = min(r, memo(a/3, mem) + 1);
    mem[a] = r;
    return r;
}

我在互联网上和 StackOverflow 上查找了这个错误，我发现当我们尝试访问尚未分配的内存时可能会发生此错误，例如访问 10 元素数组的第 11 个元素.但我不认为这里是这种情况。

另外，我认为问题的上限是2*10^7，而且数组是全局的，所以应该不是问题。也许我使用 memset 函数的方式有问题？我真的不知道!

任何帮助将不胜感激!感谢阅读!

Answer 1

您的 DP 想法是正确的，但您的代码不适用于大输入(例如 1x10^6，或上限 2x10^7)。

通过稍微更改您的代码，您可以预先计算每个答案，然后仅输出您感兴趣的答案。由于问题的动态编程方式，它不会很耗时，即一个复杂的问题可以作为一个或多个先前解决的问题的组合来解决。

int main() 
{
    // Initialize DP array
    memset(mem, -1, sizeof(mem));
    mem[1] = 0;

    // Pre-compute every possible answer
    for(int i = 2; i <= 20000000; i++)
        mem[i] = memo(i);

    // Read the number of test cases
    int t;
    scanf("%d", &t);

    // Print only the desired answer, ie, mem[n]
    for(int i = 1; i <= t; i++) {
        int n;
        scanf("%d", &n);
        printf("Case %d: %d\n", i, mem[n]);
    }

    return 0;
}

我通过这种方法获得了录取。

另一个提示:由于您的 DP 数组是全局的，因此您不必每次都将它传递给 DP 函数。