用于动态编程的C++动态数组

Question

我正在解决动态编程问题.问题是使用尽可能少的项将整数分解为平方数之和.一个标准的DP问题,我提出了一个程序:

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

}

我测试了一下,代码工作.以下是一些测试结果:

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

然后我尝试使用动态数组替换dp数组.这样做的原因是在一些OJ站点中,堆栈空间有限.

具体来说,我所做的是将第3行更改为

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

并添加

delete [] dp; 

在返回结果之前.

但是,我的代码在更改后不再起作用.此更改不会影响算法本身.我想我创建的动态数组的内存在for循环中被破坏了.但我无法理解问题的确切位置.

Answer 1

问题恰好在您定义数组的行中: int *dp = new int(num+1);这意味着您创建一个指向整数值的指针,例如int,初始化num+1为不是您想要的值.要创建数组,您需要使用括号[].

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

这将创建一个int具有大小的元素数组num+1.