程序在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