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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告