程序在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 要庆祝生日祝福语简短