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

假设我们有一个二维二进制矩阵和另一个值k。现在从左上角单元格开始，我们必须到达右下角单元格。一步只能向下或向右移动。一条路径的分数是路径上单元格值的总和。我们必须找到从起始单元格到结束单元格且分数为k的路径数。如果可能的路径数量巨大，则返回结果模10^9+7。

因此，如果输入如下所示：

001
101
010

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 := 矩阵的行数，n := 矩阵的列数

  • 定义一个函数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

示例

让我们看下面的实现以更好地理解：

在线演示

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

更新于：2020年12月22日

257 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告