c++ - 较高 n 值的段错误(例如 n=999997)

Question

我正在使用动态编程来解决一个问题，其中我将得到 n 并且需要输出最小数量的操作以通过使用这三个操作(-1，/2，/3)从 n 中获得 1。给定约束(1<=n<=10^6)
我的代码是 段错误(在求解函数中)对于较高的 n 值(例如 977775,1000000)，但在较小的输入(例如 100000)下运行良好。
我已经尝试了很多，但我无法在我的代码中找到问题。还有其他方法可以在这个问题中应用动态编程。
任何帮助，将不胜感激。

#include<iostream>
using namespace std;
int solve(int n,int a[])
{
    if(n==1)
    return 0;
    if(a[n]!=-1)
    return a[n];
    int ans=100000;
    for(int i=0;i<3;i++)
    {
        if(i==0)
        {
            a[n]=solve(n-1,a)+1;
            if(a[n]<ans)
            ans=a[n];
        }
        else if(i==1 && n%2==0)
        {
            a[n]=solve(n/2,a)+1;
            if(a[n]<ans)
            ans=a[n];
        }
        else if(i==2 && n%3==0)
        {
            a[n]=solve(n/3,a)+1;
            if(a[n]<ans)
            ans=a[n];
        }
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    int a[n+1];
    for(int i=0;i<=n;i++)
    a[i]=-1;
    int ans=solve(n,a);
    cout<<ans<<endl;
    return 0;
}

Answer 1

问题是您只能在 C++ 中的 int 变量中存储最多 8 位数字，我会从 int ans 切换到 double ans 来解决问题，还请记住，如果您尝试使用 double 最多可以存储 34 位数字确实存储的位数超过了允许的最大位数，奇怪的事情发生了，在这种情况下你会得到一个 stackOverflow .....还要考虑以下几点:在你的函数中，你正在调用大约 999997 recusive calls * 3 这大约是堆栈的 3000000 次递归调用，这将使用太多内存，因此段错误.....