查找 0 和 1 矩阵中的路径总数

Question

我正在开发一个程序，该程序指出：

\n\n

给定一个包含 M 行和 N 列的二维矩阵。您最初位于 (0,0)，这是数组中左上角的单元格。您可以向右或向下移动。该数组由 1\xe2\x80\x99s 和 0\xe2\x80\x99s 填充。1 表示您可以在该单元格中移动，0 表示您无法在该单元格中移动。返回从左上角单元格到右下角单元格的路径数（即（0,0）到（M-1,N-1））。由于答案可能很大，因此您必须返回 ans%(10^9+7)。

\n\n

我尝试实现它，它在某些情况下有效，但在某些情况下失败：

\n\n

static int count(int a[][], int i, int j) {\n    int rows = a.length;\n    int cols = a[0].length;\n    if(a[i][j] == 0)  return 0;\n    if (i == rows - 1 && j == cols - 1)\n        return a[i][j];\n    else if (i == rows - 1)\n        return a[i][j + 1];\n    else if (j == cols - 1)\n        return a[i + 1][j];\n    else if (a[i][j] == 1)\n        return count(a, i + 1, j) + count(a, i, j + 1);\n    else\n        return 0;\n}\n

\n\n

以下数组失败：\n{{1,1}, {0,1}}

\n\n

您能帮我看看这个程序有什么问题吗？

\n\n

更新：

\n\n

感谢@Johnny Mopp，它解决了上述测试用例。我们怎样才能提高这个程序的性能呢？

\n

Answer 1

首先 if 应该检查 的值a[i][j]。如果是 0，你应该返回 0。

关于性能，以这种方式编写的算法非常慢，因为您多次计算相同的值。使用记忆（创建第二个数组并保存返回的每个值，如果您之前没有计算过，请在函数开始时首先检查）或使用动态编程来解决它。

编辑：你忘记了你的模 10^9+7。

第二次编辑（回应你的评论）：就像那样。我将其分为三个循环，以便主（第三）循环执行的操作较少，并且对于大数据来说，功能速度相当快。我还改变了计算方向，但这根本不重要。

static int count_dp(int a[][]){
    int rows = a.length;
    int cols = a[0].length;
    int[][] dp = new int[rows][cols];

    dp[0][0] = a[0][0];

    for(int i=1;i<rows;i++)
        if(dp[i-1][0]==1 && a[i][0]==1)
            dp[i][0] = 1;

    for(int i=1;i<cols;i++)
        if(dp[0][i-1]==1 && a[0][i]==1)
            dp[0][i] = 1;

    for(int i=1;i<rows;i++)
        for(int j=1;j<cols;j++)
            if(a[i][j]==1)
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000007;

    return dp[rows-1][cols-1];
}