机器人移动路径数量：动态规划算法详解

问题描述： 一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求它从(0,0)移动到(m,n)有多少条路径。

算法说明： 使用动态规划的思想，设dp[i][j]表示从(0,0)移动到(i,j)的路径条数。由于机器人只能向下或向右移动，所以机器人到达(i,j)的路径只能从(i-1,j)或(i,j-1)两个位置到达。因此递推公式为dp[i][j]=dp[i-1][j]+dp[i][j-1]，边界条件为dp[0][0]=1，dp[i][0]=1，dp[0][j]=1。最终结果为dp[m][n]。

程序源码：

def uniquePaths(m: int, n: int) -> int:
    dp = [[0] * n for i in range(m)]
    dp[0][0] = 1
    for i in range(1, m):
        dp[i][0] = 1
    for j in range(1, n):
        dp[0][j] = 1
    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]

运行结果截图：

运行结果截图

时间复杂度分析： 该算法使用了一个二维数组dp，时间复杂度为O(mn)。