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