Python程序：查找从左上角到右下角的路径数

假设我们有一个N x M的二进制矩阵。其中0表示空单元格，1表示阻塞单元格。现在从左上角开始，我们必须找到到达右下角的方法数量。如果答案非常大，则将其模10^9 + 7。

因此，如果输入如下所示：

001
000
110

则输出为2，因为到达右下角有两种方法：[右，下，右，下]和[下，右，右，下]。

为了解决这个问题，我们将遵循以下步骤：

  • dp := 与给定矩阵大小相同的矩阵，并填充0
  • dp[0, 0] := 1
  • 对于范围从1到矩阵行数的i，执行：
    • 如果matrix[i, 0]等于1，则
      • 退出循环
    • 否则，
      • dp[i, 0] := 1
  • 对于范围从1到矩阵列数的j，执行：
    • 如果matrix[0, j]等于1，则
      • 退出循环
    • 否则，
      • dp[0, j] := 1
  • 对于范围从1到矩阵行数的i，执行：
    • 对于范围从1到矩阵列数的j，执行：
      • 如果matrix[i, j]等于1，则
        • dp[i, j] := 0
      • 否则，
        • dp[i, j] := dp[i - 1, j] + dp[i, j - 1]
  • 返回dp的右下角的值

示例（Python）

让我们看看下面的实现，以便更好地理解：

 在线演示

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

输入

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]

输出

2

更新于：2020年12月12日

340 次浏览

启动您的职业生涯

通过完成课程获得认证

开始
广告