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

Question

我正在学习动态规划。我正在尝试解决以下问题:

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

任务 给定一个整数 n，计算获得数字 n 所需的最少操作次数 从数字 1 开始。 输入由单个整数 1 < n < 10^6 组成。

代码

#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];

1. 它在堆栈上创建了一个std::list变量数组，所以如果数量很大，堆栈就会溢出并出现段错误。
2. 此代码收到来自 GCC 的警告:

   warning: ISO C++ forbids variable length array 'path' [-Wvla]

3. 它也被 clang 拒绝了:

   error: variable length array of non-POD element type 'std::list'

因此不要在堆栈上定义巨大的变量。

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

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

那么你的问题就解决了。