为什么我的程序在大量输入时失败了？超过10^5

Question

我正在学习动态编程，我想解决以下问题：

问题介绍：给你一个基元计算器，它可以用当前数x执行以下三种操作：x乘以2，x乘以3，或者1加到x。你的目标是给定一个正整数n，从数字1开始，找出获得数字n所需的最小运算次数。

任务给定一个整数n，计算从数字1开始获得数字n所需的最小操作数。输入由单个整数1

代码

#include <iostream>
#include <climits>
#include<vector>
#include<list>
void primitive_calculator(int number)
{
    std::vector<int> min_steps(number+1,INT_MAX);
    std::list<int> path[number+1];
    min_steps[0]=0; min_steps[1]=0;
    path[0].push_back(0);
    path[1].push_back(1);
    for (int i=2 ; i<=number ; i++)
    {
        if(i%3==0)
        {
            if(min_steps[i/3] < min_steps[i])
            {
                min_steps[i]=min_steps[i/3]+1;
                path[i]=path[i/3];
                path[i].push_back(i);
            }
        }
        if(i%2==0)
        {
            if( min_steps[i/2] < min_steps[i])
            {
                min_steps[i]=min_steps[i/2]+1;
                path[i]=path[i/2];
                path[i].push_back(i);
            }
        }

        if( min_steps[i-1] < min_steps[i])
        {
             min_steps[i]=min_steps[i-1]+1;
             path[i]=path[i-1];
             path[i].push_back(i);
        }
    }
    std::cout<<min_steps[number]<<"\n";
    while(!path[number].empty())
    {
        std::cout<<path[number].front()<<" ";
        path[number].pop_front();
    }

}
int main()
{
    int number;
    std::cin>>number;
    primitive_calculator(number);
    return 0;
}

此程序因输入数大于10^5而失败。为什么会这样？如何改进代码？

Answer 1

您的问题已联机：

std::list<int> path[number+1];

>

它会在堆栈上创建一个std::list变量数组，因此如果数量很大，堆栈会溢出并出现段错误。

此代码从gcc获得警告：

警告：ISO C++禁止可变长度数组“path”[-wvla]

错误：非POD元素类型“std：：list”的可变长度数组

所以不要在堆栈上定义巨大的变量。

相反，您应该做的是使用std::vector，例如将行更改为：

std::vector<std::list<int>> path(number+1);

那你的问题就解决了。