一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
分析：m表示列，n表示行
以示例2举例
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 3 | 6 | 10 | 15 | 21 | 18 |
解法一：用一个n * m的二维数组result来表示上表中元素，其中result[i][j]表示从原点出发到达第i行,第j列的路径总数
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
result = [[0 for i in range(m)] for j in range(n)]
#用0初始化二维数组
for i in range(m):
result[0][i] = 1
#第一行元素全为1，只有一条路径，从原点一直往右走
for j in range(n):
result[j][0] = 1
#第一列元素全为1，只有一条路径，从原点一直往下走
for i in range(1,n):
for j in range(1,m):
result[i][j] = result[i][j-1] + result[i-1][j]
#除第一行第一列，其余所有点的值由前一行同一列加前一列同一行所得
return result[n-1][m-1]
解法二：和解法一思路相同，只是用两个一维数组来表示，解法一的空间复杂度为O(n * m)解法二的空间复杂度为O(2 * m)当然也可以换为O(2 * n)
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
pre = [1] * m
#初始化第一行
for i in range(n-1):
last = [1] + [0] * (m-1)
#初始化第二行
for j in range(1,m):
last[j] = last[j-1] + pre[j]
pre = last
#将后一行的值赋给钱一行
return pre[-1]
解法三：总需要走(m + n - 2)步，其中(m -1)步向右，(n-1)步向下，是一个排列组合问题
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
t = m + n - 2
down = 1
#分子
up =1
#分母
for i in range(1,n):
down *= i
up *= t
t -= 1
return up//down