arrays - 计算二维数组中从 arr[0,0] 到 arr[N,M] 的路径数，其中只能向右和向下移动

Question

给定一个大小为 [N,M] 的二维数组，计算从“左上角” (arr [0, 0]) 到数组的“右下角”(arr[N - 1, M - 1])。

Answer 1

我们将使用递归解决方案，其中:

1)停止条件会返回:

• 1，如果我们到达arr[N,M]。

• 0，如果我们超出了数组的“边界”。

2) 递归调用将再次调用该函数，一次是我们向右移动的地方，一次是我们向下移动的地方。

注意:dim1 和 dim2 总是以数组的原始大小 (N,M) 发送。

递归函数的实现将是:

int numOfPathsToEndOfTwoDimMatrix(int x, int y, int dim1, int dim2)
{
    if (x == dim1 - 1 && y == dim2 - 1)
    {
        return 1;
    }

    if (x > dim1 - 1 || y > dim2 - 1)
    {
        return 0;
    }

    return numOfPathsToEndOfTwoDimMatrix(x + 1, y, dim1, dim2) + numOfPathsToEndOfTwoDimMatrix(x, y + 1, dim1, dim2);
}

函数的调用如下:

void main(int argc, char** argv)
{
    int n = 3;
    int m = 3;
    printf("numOfPathsToEndOfTwoDimMatrix(0,0, %d, %d) returned:%d \n", n, m, 
    numOfPathsToEndOfTwoDimMatrix(0,0, n, m));
}