Рекурсивная функция, генерирующая экземпляр 'std :: bad_allo c' - PullRequest
Новая
       106

Рекурсивная функция, генерирующая экземпляр 'std :: bad_allo c'

0 голосов
/ 01 мая 2020

Проблема в том, чтобы отрезать стержень во всех этих слабых местах. Срезы могут быть выполнены в любом порядке. После разреза стержень разделяется на две меньшие подстержни. Стоимость изготовления выреза - это длина вспомогательного стержня, в котором сделан разрез. Цель состоит в том, чтобы минимизировать затраты и вернуть лексикографически наименьшую последовательность разрезов. 

   Constraints: N <=10^9

Код создает экземпляр 'станд :: bad_allo c'. Платформа выдает эту ошибку во время выполнения. Проблема заключается не в оптимальном использовании памяти, поскольку платформа выдает разные сообщения для одного и того же. Утечка памяти не может быть идентифицирована. Есть ли другие причины для такого поведения?

Код выглядит следующим образом: 

        int cut(int i,int j,vector<int> &B,vector<vector<int>> &dp,vector<vector<int>> &index){
               if(dp[i][j]!=-1){
                    return dp[i][j];
               }
              if(j == i+1){
                    return dp[i][j] = 0;
               }
              int ind = -1;
              int curr = 0,minCost = INT_MAX;
              for(int k = 0 ; k < B.size();k++){
                    if(B[k] > i && B[k] < j){
                           curr = (j-i) + cut(i,B[k],B,dp,index) + cut(B[k],j,B,dp,index);

                          if(curr< minCost){
                             minCost = curr;
                             ind = B[k];
                          }
                   }
              }
              if(minCost == INT_MAX){
                 minCost = 0;
              }else{
                 index[i][j] = ind;
              }
              return dp[i][j] = minCost;

     }

     void fill(vector<int> &res1,vector<vector<int>> &index,int i,int j){
        if(j == i+1 || index[i][j] == -1)
           return ;
        res1.push_back(index[i][j]);
        fill(res1,index,i,index[i][j]);
        fill(res1,index,index[i][j],j);

     }

Это основной метод, с которого начинается выполнение 

    vector<int> Solution::rodCut(int A, vector<int> &B) {

              vector<vector<int>> dp(A+1,vector<int>(A+1,-1));
              vector<vector<int>> index(A+1,vector<int>(A+1,-1));
              vector<int> res1;
              int cost = cut(0,A,B,dp,index);

              fill(res1,index,0,A);
              return res1;
   }
...