程序在Python中从起点到终点对成本为k的路径数进行计数

假设我们有一个二维二进制矩阵和另一个值k。现在从左上方的单元格开始，我们必须转到右下方的单元格。一步，我们只能走下去，或者走对。现在，路径的分数是路径上单元格的值之和。我们必须找到从起始单元格到终止单元格得分为k的路径数。如果有很多可能的方法，则返回结果mod 10 ^ 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