在Python中计算从起点到终点的成本为k的路径数量的程序
假设我们有一个二维二进制矩阵和另一个值k。现在从左上角的单元格开始,我们必须走到右下角的单元格。在一步中,我们只能向下或向右走。现在路径的分数是路径上单元格值的总和。我们必须找到从开始单元格到结束单元格的路径数,带有分数k。如果存在大量可能的路径,则返回结果mod 10 ^ 9 + 7。
因此,如果输入类似
0 | 0 | 1 |
---|---|---|
1 | 0 | 1 |
0 | 1 | 0 |
K = 2,那么输出将为4,因为分数为2的路径为[R,R,D,D],[D,R,R,D],[D,D,R,R],[D,R,D,R],其中D为向下,R为向右。
要解决这个问题,我们将遵循以下步骤:
- deno := 10^9 + 7
-
m := matrix的行数,n := matrix的列数
-
定义一个函数dfs()。这将采用i,j,pts
-
如果i≥m或j≥n,则
- 返回0
- pts := pts + matrix[i, j]
-
如果i与m-1相同且j与n-1相同,则
- 如果pts与k相同,则返回1,否则返回0
- 返回dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
-
从主方法执行以下操作−
-
返回dfs(0, 0, 0) mod deno
更多Python相关文章,请阅读:Python 教程
例子
让我们看一下以下实现,以获得更好的理解−
class Solution:
def solve(self, matrix, k):
m, n = len(matrix), len(matrix[0])
def dfs(i=0, j=0, pts=0):
if i >= m or j >= n:
return 0
pts += matrix[i][j]
if i == m - 1 and j == n - 1:
return int(pts == k)
return dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
return dfs() % (10 ** 9 + 7)
ob = Solution()
matrix = [
[0, 0, 1],
[1, 0, 1],
[0, 1, 0]
]
k = 2
print(ob.solve(matrix, k))
输入
[
[0, 0, 1],
[1, 0, 1],
[0, 1, 0]
], 2
输出
4