0

So I'm practicing solving DP problems and found out this issue I couldn't comprehend why. If I initialize my vector of vectors with size n, operations won't work. Meanwhile if I just declare cost as int cost[n][n] it does. Please tell me why.

int sum (vector<int> freq, int i, int j){

   int s=0;
   for (int x=i; x<=j; x++) {
     s+=freq[x];
   }

 return s;
}

int optimalSearchTree(vector<int> keys, vector<int> freq){


  int n = keys.size();
  vector<vector<int>> cost( n,vector<int>( n,0 )) ;




  for (int i = 0; i < n; i++) {
    cost[i][i] = keys[i];
  }

  for (int L=2; L<=n; L++) {

     for (int i = 0; i<= n-L+1; i++) {

        int j = i+L-1;
        cost[i][j] = INT_MAX;

        for (int r=i; r<=j; r++) {


            int c = ((r > i)? cost[i][r-1]:0) +
                    ((r < j)? cost[r+1][j]:0) +
                    sum(freq, i, j);

            if (c < cost[i][j]) {
                cost[i][j] = c;
            }

        }
      }
  }

  return cost[0][n-1];
 }


int main(){

vector<int> keys = {10,12,16,21};
vector<int> freq = {4,2,6,3};

cout<<optimalSearchTree(keys, freq)<<endl;

 // int n = keys.size();
//vector<vector<int>> cost( n,vector<int>( n,0 )) ;

//cout<<cost.size()<<" "<<cost[0].size()<<endl;


}
Gustavo
  • 190
  • 2
  • 14

1 Answers1

0

I believe the solution follows the same as this question:

Accessing an array out of bounds gives no error, why?

In it, specifies that out of bound access from a int arr[n][n] won't return any error. Meanwhile accessing out of bound positions from a vector will.

Community
  • 1
  • 1
Gustavo
  • 190
  • 2
  • 14