Dynamic array in C++ for dynamic programming

Question

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.

@paul R, std::vector<int> will definitely work. I just couldn't understand why changing to dynamic array will fail the whole program. — wakeupbuddy
– wakeupbuddy, Commented Feb 3, 2015 at 8:14
As a side note, your original int dp[num+1]; is not standard C++ when num is not a constant expression (supported in C99 and as a compiler extension in some C++ compilers). — crashmstr
– crashmstr, Commented Feb 3, 2015 at 17:47

KiaMorot · Accepted Answer · 2015-02-03 08:37:11Z

6

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.

edited Feb 3, 2015 at 8:37

answered Feb 3, 2015 at 8:16

KiaMorot

1,75611 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

KiaMorot Over a year ago

If you problem is solved you should accept this answer so that we lower the number of unanswered Q/A.

wakeupbuddy Over a year ago

done. sorry, I am a newbie here so it take me a while to figure out how to accept your answer.

Collectives™ on Stack Overflow

Dynamic array in C++ for dynamic programming

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related