极客教程在 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
- if matrix[i, 0] equals 1, then
- for j in range 1 to 矩阵的列数, do
- if matrix[0, j] equals 1, then
- 退出循环
- 否则,
- dp[0, j] := 1
- if matrix[0, j] equals 1, then
- 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]
- for j in range 1 to 矩阵的列数, do
- 返回 dp 的右下角值
更多Python相关文章，请阅读：Python 教程
示例（Python）
让我们看看以下实现以更好地理解 –