Python中的唯一路径

假设有一个机器人位于anxm网格的左上角（n行m列）。机器人在任何时间点只能向下或向右移动。机器人希望到达网格的右下角（在下图中标记为“ END”）。因此，我们必须找到多少个唯一的路径？例如，如果m = 3且n = 2，则网格将如下所示-

输出将为3，因此从开始位置到结束位置共有3种不同的到达方式。这些路径是-

1. 右→右→下

2. 右→下→右

3. 下→右→右

让我们看看步骤-

• 我们将使用动态编程方法来解决此问题

• 让row：= n和col：= m，创建nxm阶的表DP并用-1填充

• DP [行– 2，列-1]：= 1

• 对于我在0到col的范围内

• DP [n – 1，i]：= 1

• 对于我在0到行的范围内

• DP [i，col – 1]：= 1

• 对于范围行-2中的i降至-1

• DP [i，j]：= DP [i + 1，j] + DP [i，j + 1]

• 对于范围col -2中的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