计算二维数组上的路径数（grid Traveller）

提问者：小点点

计算二维数组上的路径数（grid Traveller）

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

我已经实现了一个递归解决方案和一个记忆化的解决方案（其中2d-Array存储已经计算的路径）。在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;
}

共2个答案

匿名用户

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

正如@Eric Postpischil所指出的，在计算路径数时，您应该使用更宽的类型，如uint64_t或无符号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}（如果需要，请查看二项式系数的定义）。

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

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

匿名用户

对int类型的res和res1 inplace使用long变量类型。

重复发现超出了int限制。