计算二维数组上的路径数（网格旅行者）

Question

我有以下内容objective：“给定一个二维 m×n 矩阵，编写一个算法来计算从左上角到右下角的所有可能路径。你只能在两个方向上移动方向，向右移动或向下移动。” 这个问题很容易分解。例如，一个 3 x 3 网格的路径数与 2 x 3 网格和 3 x 2 网格的总和一样多。所以递归解决方案非常直观。

我已经实现了一个递归解决方案和一个带有记忆的解决方案（其中二维数组存储已计算的路径）。在 C 中，但不知何故，当网格变得太大时，两者的功能仍然 return 相同，但负解决方案（即 15 x 15 工作正常，18 x 18，不再）。知道这是从哪里来的吗？我的代码附在下面。另外.. 有没有一种很好的方法来编写记忆解决方案的数组？如果我使用 A[m][n] 作为函数参数，它不太有效，所以我暂时将其硬编码。

谢谢！

#include <stdio.h>

int gridTravel(int m, int n){
    if (m == 0 || n == 0){
        return 0;
    }
    if (m == 1 || n == 1){
        return 1;
    }
    return gridTravel(m-1, n) + gridTravel(m, n-1);
}

int gridTravelMemo(int m, int n, int A[15][15]){
    if (m == 0 || n == 0){
        return 0;
    }
    if (m == 1 || n == 1){
        return 1;
    }
    if (A[m-1-1][n-1] == 0){
        A[m-1-1][n-1] = gridTravelMemo(m-1, n, A);
    }
    if (A[m-1][n-1-1] == 0){
        A[m-1][n-1-1] = gridTravelMemo(m, n-1, A);
    }
    return  A[m-1-1][n-1] + A[m-1][n-1-1];
}

int main(){
    int res = gridTravel(15,15);
    printf("There is a total of %d ways to traverse the grid (Grid size is 15 by 15).\n", res);

    int res2 = gridTravel(18,18);
    printf("There is a total of %d ways to traverse the grid (Grid size is 18 by 18).\n", res2);
    
    int A[15][15] = {0};
    int res_memo = gridTravelMemo(15,15,A);
    printf("There is a total of %d ways to traverse the grid (Grid size is 15 by 15).\n", res_memo);

    return 0;
}

Answer 1

对 res 和 res 1 使用 long 变量类型代替 int 类型。

递归发现超出了 int 限制。

Answer 2

我不会在这里使用任何动态规划或递归，而是宁愿使用组合数学来解决它。

正如@Eric Postpischil 所指出的，在计算路径数量时，您应该使用更宽的类型，例如 uint64_t 或 unsigned long long 或类似的类型。

解释

你要问的是，长度为 m - 1 + n - 1 的路径有多少可以从左上角开始到右下角结束。为什么 m + n - 2？

嗯，因为你只能向右或向下移动。最初，您距离目标 m - 1 行和 n - 1 列。每一步，您都会使 1 行或 1 列更接近目标。因此，您需要准确执行 m + n - 2 步。

但是有多少种组合呢？在 m + n - 2 步中，您必须向下走 m - 1 步，向右走 n - 1 步。因此，从 m + n - 2 步中采取 m - 1 垂直步长（或 n - 1 水平步长）的方法数是 C^m-1_m+n-2 或 C^n-1_m+n-2（请看如果需要，可在此处定义 Binomial coefficient。

公式

下面的两个公式产生相同的结果

C^m-1_m+n-2

C^n-1_m+n-2

代码

然后，您的方法可以重新实现如下。请注意，如果 n 和 m 变得相对较大，您可能会遇到溢出。另外，我对二项式系数的实现不是最优的。

#define MIN(a,b) (((a)<(b))?(a):(b))

uint64_t gridTravel(uint64_t m, uint64_t n) {
    if (m == n && m == 1) {
        return 0;
    }

    uint64_t result = 1;
    for (uint64_t i = 1; i <= MIN(m - 1,n - 1); i++) {
        result *= (m + n - 1 - i);
        result /= i;
    }

    return result;
}

计算二维数组上的路径数（网格旅行者）

Count number of paths on 2d-array (grid Traveller)

c

arrays

algorithm

recursion

dynamic-programming

解释

公式

代码