一个机器人只能向下和向右移动,每次只能移动一步,设计一个算法求它从(0,0)移动到(m,n)有多少条路径。
时间: 2023-04-27 21:06:33 浏览: 359
DSP中的一种移动机器人的路径规划算法分析
这是一个经典的动态规划问题。我们可以用一个二维数组dp来记录到达每个位置的路径数。其中dp[i][j]表示从起点(0,0)到达位置(i,j)的路径数。
初始化dp数组的第一行和第一列,因为机器人只能向下或向右移动,所以第一行和第一列的路径数都为1。
然后,我们可以使用递推公式来计算dp数组的其他元素。对于位置(i,j),它可以从上方位置(i-1,j)或左侧位置(i,j-1)到达,因此dp[i][j] = dp[i-1][j] + dp[i][j-1]。
最后,dp[m][n]就是从起点到达终点的路径数。
下面是Python代码实现:
```
def uniquePaths(m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
```
时间复杂度为O(mn),空间复杂度为O(mn)。
阅读全文