描述
有一个机器人的位于一个 m × n 个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径？
注意：n和m均不超过100，且答案保证在32位整数可表示范围内。
在线评测地址：领扣题库官网
样例 1:
Input: n = 1, m = 3
Output: 1
Explanation: Only one path to target position.样例2：
Input: n = 3, m = 3
Output: 6
Explanation:
D : Down
R : Right
1) DDRR
2) DRDR
3) DRRD
4) RRDD
5) RDRD
6) RDDR挑战
要求时间复杂度为 O(n)
解题思路
不难发现，机器人从左上角走到右下角，需要向下走m - 1步，向右走n - 1步，那么总步数也是一定的，为m + n - 2步。问题就转化成，从m + n - 2步中选出m - 1步向下，其余步数自然是向右，有多少种组合？
利用我们中学的知识可知，答案是
根据组合公式，有
计算三数的阶乘，我们就能得出答案。我们还可以进行一定的优化，展开成上述公式的最右项。设m < n，那么时间复杂度就只有O(m)。
复杂度分析
时间复杂度: O(min(m,n))。计算阶乘的时间复杂度与m, n中的较小数成线性关系。
空间复杂度:O(1)。常量空间。
class Solution:
"""
@param m: positive integer (1 <= m <= 100)
@param n: positive integer (1 <= n <= 100)
@return: An integer
"""
def uniquePaths(self, m, n):
# corner case
if (m == 1 or n == 1):
return 1
# 保证m <= n
if (m > n):
m, n = n, m
# 计算阶乘
temp = 1
res = 1
for i in range(1, m):
temp *= i
for i in range(n, m + n - 1):
res *= i
return res//temp动态规划
解题思路
建立二维数组dp，令dpi表示到达 i, j的最多路径数。
初始化：对于第一行 dp0，或者第一列 dpi，都只有一条路径。
机器人到达位置(i, j)有两种方式：从(i - 1, j)下移和从(i, j - 1)右移。状态转移方程为：
复杂度分析
时间复杂度：O(mn)。遍历dp数组进行动态规划。
空间复杂度：O(mn)。创建的dp数组的大小。
代码
class Solution:
"""
@param m: positive integer (1 <= m <= 100)
@param n: positive integer (1 <= n <= 100)
@return: An integer
"""
def uniquePaths(self, m, n):
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]优化后的动态规划
dp可以优化为一维滚动数组。当第i次遍历到dp[j]时，dp[j]表示到达(i, j)最多的路径数。递推公式为：dp[j]+=dp[j−1]。
复杂度分析
时间复杂度：O(mn)。遍历dp数组进行动态规划。
空间复杂度：O(n)。创建的一维dp数组的大小。
代码
class Solution:
"""
@param m: positive integer (1 <= m <= 100)
@param n: positive integer (1 <= n <= 100)
@return: An integer
"""
def uniquePaths(self, m, n):
dp = [0] * n
dp[0] = 1
for i in range(m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]更多题解参考：九章官网solution
