Python中的唯一路徑

假設有一個機器人位於n x m網格（n行m列）的左上角。機器人每次只能向下或向右移動。機器人想要到達網格的右下角（下圖中標有“END”）。所以我們必須找到有多少種可能的唯一路徑？例如，如果m = 3且n = 2，則網格如下所示：

機器人



終點(END)

輸出將是3，因此共有3種不同的方法可以從起始位置到達終點位置。這些路徑是：

  1. 右 → 右 → 下
  2. 右 → 下 → 右
  3. 下 → 右 → 右

讓我們看看步驟：

  • 我們將使用動態規劃方法來解決這個問題
  • 令row := n，col := m，建立一個n x m階的DP表，並將其填充為-1
  • DP[row – 2, col - 1] := 1
  • 對於i從0到col
    • DP[n – 1, i] := 1
  • 對於i從0到row
    • DP[i, col – 1] := 1
  • 對於i從row -2遞減到-1
    • 對於j從col -2遞減到-1
      • DP[i, j] := DP[i + 1, j] + DP[i, j + 1]
  • 返回DP[0, 0]

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

class Solution(object):
   def uniquePaths(self, m, n):
      row = n
      column = m
      dp = [[-1 for i in range(m)] for j in range(n)]
      dp[row-2][column-1] = 1
      for i in range(column):
         dp[n-1][i] = 1
      for i in range(row):
         dp[i][column-1]=1
      for i in range(row-2,-1,-1):
         for j in range(column-2,-1,-1):
            dp[i][j] = dp[i+1][j] + dp[i][j+1]
      return dp[0][0]
ob1 = Solution()
print(ob1.uniquePaths(10,3))

輸入

10
3

輸出

55

更新於：2020年5月4日

617 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告