在Python中计算从起点到终点的成本为k的路径数量的程序

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程