I am getting this strange compilation error in C++

Question

I was doing the Coin change problem, I am trying to do it using Dynamic Programming. But I am getting this compilation which I don't quite understand. Someone told me that I have to assign the 'dp' array dynamically, but he was not sure why. PLease explain this concept .

#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 );
    

}

Error :

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);
                                                            ^

Here is my Main file code:

#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

There are two problems in the code.

First, in the function int countWaysToMakeChange(int denominations[], int numDenominations, int value)

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

is illegal. Array bounds must be compile-time constants. Some compilers allow this sort of things as an extension (and it's legal in C), but it is not valid C++.

Second, the type of dp is "array of array of int". It is not a "pointer to pointer to int", and the compiler is complaining that it can't make that conversion when the code tries to pass dp as the fourth argument to solve.

Arrays are confusing. In most contexts, the name of an array decays into a pointer to its first element. That's why you can write code like this:

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

Since dp is an array, its name decays into a pointer to its first element. But this is where it's easy to get lost: as I said earlier, the type of dp is "array of array of int"; when its name decays, the resulting type is "pointer to array of int".

If you want to pass dp to solve, solve has to take the same type: "pointer to array of int". But since you don't know the size of that array when you write solve you can't write that type in the argument list.

That's one reason why multi-dimensional arrays are often represented as one-dimensional arrays, with code to convert the two dimensions into one. The offset is x * width + y, or some minor variant on that. When you do that, your two-dimensional array becomes a one-dimensional array, and its name decays into a pointer to its first element, so you can pass it to a function that expects int*.