程序在Python中从起点到终点对成本为k的路径数进行计数
假设我们有一个二维二进制矩阵和另一个值k。现在从左上方的单元格开始，我们必须转到右下方的单元格。一步，我们只能走下去，或者走对。现在，路径的分数是路径上单元格的值之和。我们必须找到从起始单元格到终止单元格得分为k的路径数。如果有很多可能的方法，则返回结果mod10^9+7。
所以，如果输入像
K=2，则输出将为4，因为得分为2的路径为[R，R，D，D]，[D，R，R，D]，[D，D，R，R]，[D,,R，D，R]这里D向下，R正确。
示例
让我们看下面的实现以更好地理解-
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
热门推荐
10 感谢韩语老师祝福语简短
11 升职文案高级祝福语简短
12 花童结婚祝福语大全简短
13 向国庆送祝福语简短
14 什么寄语简短祝福语女生
15 客户回礼祝福语大全简短
16 女孩生日祝福语简短创意
17 家长回复节日祝福语简短
18 给外婆敬酒祝福语简短