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

Question

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

我已经实现了一个递归解决方案和一个具有记忆功能的解决方案（其中二维数组存储已计算的路径）。在 C 中，但不知何故，当网格变得太大时，两个函数仍然返回相同的负解（即 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

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

正如 @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 - 1

步中取出

n - 1

垂直步（或

m + n - 2

水平步）的方法数为 C^m-1_m+n-2 或 C^n-1_{m +n-2}（如果需要请查看二项式系数的定义）。

公式

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

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

Answer 2

对 res 和 res1 使用

long

数据类型代替

int

类型。

递归发现超出了

int

限制。