在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