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

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

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

所以,如果输入是这样的:

0 0 1
0 0 0
1 1 0

那么输出将是 2,因为有两种方法可以到达右下角:[右,下,右,下] 和 [下,右,右,下]。

为了解决这个问题,我们需要按照以下步骤进行:

  • dp := 与给定矩阵相同大小的矩阵,并填充为 0
  • dp[0, 0] := 1
  • for i in range 1 to 矩阵的行数, do
    • if matrix[i, 0] equals 1, then
      • 退出循环
    • 否则,
      • dp[i, 0] := 1
  • for j in range 1 to 矩阵的列数, do
    • if matrix[0, j] equals 1, then
      • 退出循环
    • 否则,
      • dp[0, j] := 1
  • for i in range 1 to 矩阵的行数, do
    • for j in range 1 to 矩阵的列数, do
      • if matrix[i, j] equals 1, then
      • dp[i, j] := 0
      • 否则,
      • dp[i, j] := dp[i – 1, j] + dp[i, j – 1]
  • 返回 dp 的右下角值

更多Python相关文章,请阅读:Python 教程

示例(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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程