我在 C++ 中遇到了这个奇怪的编译错误

Question

我正在做硬币找零问题，我正在尝试使用动态规划来做。但是我得到了这个我不太明白的汇编。有人告诉我必须动态分配 'dp' 数组，但他不确定为什么。请解释一下这个概念。

#include<bits/stdc++.h>
using namespace std;
int solve(int *d, int size, int n , int ** dp){
    if(n==0)
        return 1;
    if(n<0)
        return 0;
    if(size == 0)
        return 0;
    if(dp[n][size]>-1)
        return dp[n][size];
    
    int x = solve(d,size,n-d[0],dp);
    int y = solve(d+1, size - 1, n, dp );
    dp[n][size] = x+y;
    return x+y;
}

int countWaysToMakeChange(int denominations[], int numDenominations, int value){


int dp[value+1][numDenominations+1];
    memset(dp, -1, sizeof dp); 
    return solve(denominations, numDenominations, value, dp );
    

}

错误：

Compilation Failed
In file included from Runner.cpp:3:0:
Solution.h: In function 'int countWaysToMakeChange(int*, int, int)':
Solution.h:28:60: error: cannot convert 'int (*)[(numDenominations + 1)]' to 'int**' for argument '4' to 'int solve(int*, int, int, int**)'
     return solve(denominations, numDenominations, value, dp);
                                                            ^

这是我的主文件代码：

#include<iostream>
using namespace std;
#include "Solution.h"

int main(){

  int numDenominations;
  cin >> numDenominations;
  int* denominations = new int[numDenominations];
  for(int i = 0; i < numDenominations; i++){
    cin >> denominations[i];
  }
  int value;
  cin >> value;

  cout << countWaysToMakeChange(denominations, numDenominations, value);

}

Answer 1

代码中有两个问题。

首先，在函数中int countWaysToMakeChange(int denominations[], int numDenominations, int value)

int dp[value+1][numDenominations+1];

是非法的。数组边界必须是编译时常量。一些编译器允许这种东西 作为扩展 （在 C 中是合法的），但它不是有效的 C++。

其次，dp的类型是“int的数组的数组”。它不是“指向 int 的指针”，编译器抱怨说当代码试图将 dp 作为第四个参数传递给 solve 时它无法进行转换.

数组令人困惑。在大多数情况下，数组的名称会退化为指向其第一个元素的指针。这就是为什么你可以这样写代码：

void f(int*);
void g() {
    int array[20];
    f(array);
}

因为 dp 是一个数组，所以它的名字退化为指向它的第一个元素的指针。但这是很容易迷路的地方：正如我之前所说，dp 的类型是“int 的数组的数组”；当它的名字衰减时，结果类型是“指向int”数组的指针。

如果要将 dp 传递给 solve，solve 必须采用相同的类型：“指向 int 数组的指针”。但是，由于在编写 solve 时不知道该数组的大小，因此无法在参数列表中写入该类型。

这就是为什么多维数组通常表示为一维数组，并使用代码将二维转化为一维的原因之一。偏移量是 x * width + y，或者是它的一些小变体。当你这样做时，你的二维数组变成一个一维数组，它的名字衰减成一个指向它第一个元素的指针，所以你可以将它传递给一个需要 int*.

的函数

我在 C++ 中遇到了这个奇怪的编译错误

I am getting this strange compilation error in C++

c++

recursion

dynamic-programming

dynamic-memory-allocation