CODEWITHSUNDEEP
c++
wakeupbuddy
wakeupbuddy

Reputation: 1061

Dynamic array in C++ for dynamic programming

I was solving a dynamic programming problem. The problem is to decompose an integer into sum of square numbers, using terms as few as possible. A standard DP problem and I come up with a program:

vector<int> decompose(int num){
unordered_map<int, vector<int>> mymap;
int dp[num+1];
for(int i=0; i <= num; i++){
    dp[i] = i;
}
int upbound = sqrt(num)+1;
for(int i=1; i <= upbound; i++){
    int sq = i*i;
    for(int j=0 ; j+sq <= num; j++){
        if(dp[j]+1 < dp[j+sq]){
            dp[j+sq] = dp[j]+1;
            if(mymap.find(j)!=mymap.end()){
                mymap[j+sq] = mymap[j];
                mymap[j+sq].push_back(sq);                    
            }
            else{
                 vector<int> tmp(1, sq);
                 mymap[j+sq] = tmp;
            }
        }
    }
}
int sum = 0;
for(int i = 0; i < mymap[num].size(); i++){
    sum += mymap[num][i];
}
for(int i = 0; i < num - sum; i++){
    mymap[num].insert(mymap[num].begin(), 1);
}
return mymap[num];

}

I test it a little bit and the code works. Below are some test results:

num: 14, decompose as: 1 4 9 
num: 13, decompose as: 4 9 
num: 12, decompose as: 4 4 4

Then I try to replace the dp array using dynamic array. The reason to do so is that in some OJ sites, the stack space is limited.

Specifically, what I did is to change line 3 to 

int *dp = new int(num+1);

and add 

delete [] dp;

before returning the result.

However, my code does not work any more after the change. The change does not affect the algorithm itself. I guess the memory of the dynamic array I created was destroyed in the for loop. But I could not understand where exactly the problem came.

Upvotes: 1

Views: 2164

Answers (1)

KiaMorot
KiaMorot

Reputation: 1746

The problem is exactly in the line where you define your array: int *dp = new int(num+1); This means you create a pointer to integer value, e.g. int, initialized to num+1 which is not what you want. To create an array you need to use the brackets [] instead.

int *dp = new int[num+1];

This creates an array of int elements with size num+1.

Upvotes: 6

Related Questions