无法使用类型 'int [m][n]' 的左值初始化类型 'int **' 的参数注意：在此处将参数传递给参数 'dp'

Question

我正在尝试 DP 问题，但我无法将 dp[m][n]（int 矩阵类型）table 作为递归函数的引用传递。如何通过呢？下面是我写的代码。

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

Answer 1

在大多数情况下，数组的名称会衰减为指向其第一个元素的指针。所以 int a[10]; 中的 a 变成了指向 int 的指针。如果数组的元素恰好是数组本身，也会发生同样的事情：名称会退化为指向第一个元素的指针。所以 int a[10][10]; 中的 a 变成了指向整数数组的指针。这就是它的全部内容：名称退化为指向第一个元素的指针。衰减后的名字是指针的名字，不是数组的名字，所以不会再衰减了。

Answer 2

如果你查看底层内存结构，你就会明白为什么编译器不允许你传递 int[m][n] 来代替 int**。

如果你有int**，你传递的是一个指向int数组的指针数组的指针。因此内存看起来像：

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

请注意 int[] 之间不一定必须连续。

如果你有一个int[m][n]，内存是这样的：

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

你有一个连续的块，其中两个数组占据了所有内存，并且实际上数组中没有指针。

因此，虽然数组 在某些条件下可以转换为指针 ，但指向数组的指针肯定不能转换为指向指针的指针。

通过这种洞察力，您还可以了解为什么编译器有时会让您使用未知边界数组 (int[])，但绝不会让您在矩阵中使用它，除非它是最后一个数组声明符（int[5][] 合法，int[][5] 不合法），因为在这种情况下它无法知道长度为 5 的数组的每个元素有多大。

以下是我的处理方法：使函数成为 template 并使矩阵的维度（m 和 n）成为模板参数，然后您可以引用数组数组（矩阵) 将这些维度作为参数，而不必担心指向任何东西的指针。这也避免了使用可变长度数组（C++ 的非标准扩展），因为矩阵边界在编译时已知。这意味着您也必须制作 uniquePaths 模板。

无法使用类型 'int [m][n]' 的左值初始化类型 'int **' 的参数注意：在此处将参数传递给参数 'dp'

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

c++

pointers

reference

dynamic-programming