cannot initialize a parameter of type 'int **' with an lvalue of type 'int [m][n]' note: passing argument to parameter 'dp' here

Question

I was trying a DP problem but I am not able to pass the dp[m][n](type of int matrix) table as a reference to the recursive function. how to pass it? Below is the code that I wrote.

class Solution {
public:
    int countPaths(int m,int n, int **dp){
       if(m==1 || n==1) return 1;
        if(dp[m][n]!=-1)return dp[m][n];
        return dp[m][n] = countPaths(m-1,n,dp)+countPaths(m,n-1,dp);
    }
    int uniquePaths(int m, int n) {
        int dp[m][n];
        memset(dp,-1,m*n*sizeof(int));
       
        return countPaths(m-1,n-1,dp);
    }
};

Arrays decays to pointers to their first element. For a simple array like `int arr[X];` then it decays to `&arr[0]` which is of the type `int *`. ***But*** if you have an array of arrays, like `int arr[M][N];` then `&arr[0]` is of the type `int (*)[N]` which is not compatible to `int **`. — Some programmer dude, Jul 10 '21 at 11:21
Besides, the problem is moot anyway since you use a non-standard and non-portable [variable-length array (VLA](https://en.wikipedia.org/wiki/Variable-length_array) which [are not part of C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). For a variable-length array use `std::vector` instead. — Some programmer dude, Jul 10 '21 at 11:22
Lastly I recommend you invest in [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to learn C++ properly, instead of using so-called "competition" or "online judge" sites, which aren't really teaching or learning resources (quite the opposite). — Some programmer dude, Jul 10 '21 at 11:23

score 3 · Accepted Answer · answered Jul 10 '21 at 12:43

If you look at the underlying memory structure you will see why the compiler isn't letting you pass int[m][n] in place of int**.

If you have int**, what you pass is a pointer to an array of pointers to arrays of ints. The memory therefore looks like:

int** -|
       V
     [ int*, int*, int*, ...]
        V     V     V
       int[] int[] int[] ...

Notice that the int[]s do not necessarily have to be continuous between themselves.

If you have an int[m][n], the memory looks like this:

int[m][n]
      |
      V
     [ [ int, int, int, ...] m times,
       [ int, int, int, ...] m times,
       [ int, int, int, ...] m times,
       ...                   ] n times

You have a contiguous block where the two arrays occupy all of the memory, and there really is no pointer in the array.

So, while an array might be convertible to a pointer under certain conditions, a pointer to an array most certainly isn't convertible to a pointer to a pointer.

With this insight you can also see why the compiler will sometimes let you use an array of unknown bound (int[]), but will never let you use it in a matrix unless it is the last array declarator (int[5][] is legal, int[][5] is not), because in this case it cannot know how big each element of the array with length 5 is.

Here's how I would go about this: make the function a template and make the dimensions of the matrix (m and n) template parameters, you can then take a reference to an array of arrays (matrix) with those dimensions as parameter and don't have to worry about pointers to anything. This also avoids the use of variable-length-arrays (a non-standard extension to C++) since the matrix bounds are known at compile time. This means you have to make uniquePaths a template, too.

score 0 · Answer 2 · answered Jul 10 '21 at 12:39

In most contexts, the name of an array decays into a pointer to its first element. So the a in int a[10]; becomes a pointer-to-int. If the elements of an array happen to be arrays themselves, the same thing happens: the name decays into a pointer to the first element. So the a in int a[10][10]; becomes a pointer-to-array-of-int. That's all there is to it: The name decays into a pointer to the first element. After the decay, the name is the name of a pointer, not the name of an array, so no further decay occurs.

cannot initialize a parameter of type 'int **' with an lvalue of type 'int [m][n]' note: passing argument to parameter 'dp' here

2 Answers2