Python中的唯一路径

假设有一个机器人位于n x m网格（n行m列）的左上角。机器人每次只能向下或向右移动。机器人想要到达网格的右下角（下图中标有“END”）。所以我们必须找到有多少种可能的唯一路径？例如，如果m = 3且n = 2，则网格如下所示：

输出将是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

Arnab Chakraborty

更新于：2020年5月4日

617 次浏览

开启你的职业生涯

完成课程获得认证

开始学习