一个机器人在mxn大小的地图的左上角(起点)。 机器人每次可以向下或向右移动。机器人要到达地图的右下角 (终点)。 可以有多少种不同的路径从起点走到终点? 备注:m和n小于等于100并保证计算结果在int范围内 数据范围:0<nm<100，保证计算结果在32位整型范围内要求:空间复杂度0(nm)，时间复杂度O(nmn) 进阶:空间复杂度0(1)，时间复杂度O(min(nm))

这是一道典型的动态规划问题。可以定义一个二维数组dp，其中dp[i][j]表示从起点走到(i,j)的路径数目。初始状态为dp[0][0] = 1。

对于每个位置(i,j)，其路径数目为从左边的位置(i-1,j)和上面的位置(i,j-1)到达该位置的路径数之和，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

最终的答案为dp[m-1][n-1]。

以下是代码实现：

def uniquePaths(m: int, n: int) -> int:
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

该算法的时间复杂度为O(nm)，空间复杂度为O(nm)。为了进一步优化空间复杂度，可以使用滚动数组的方法将二维数组压缩成一维数组，从而将空间复杂度优化为O(min(n,m))，代码如下：

def uniquePaths(m: int, n: int) -> int:
    if m > n:
        m, n = n, m
    dp = [1]*m
    for j in range(1, n):
        for i in range(1, m):
            dp[i] += dp[i-1]
    return dp[m-1]