1、题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
2、代码
def uniquePaths(self, m, n):
"""动态规划
每一步只能从向下或者向右移动一步，因此要想走到 (i,j)(i, j)(i,j)，如果向下走一步，那么会从 (i−1,j)(i-1, j)(i−1,j) 走过来；如果向右走一步，那么会从 (i,j−1)(i, j-1)(i,j−1) 走过来。
因此我们可以写出动态规划转移方程：f(i,j)=f(i−1,j)+f(i,j−1)
"""
# [0]*(n-1)for _ in range(m-1)组成m-1行,n-1列
# [[1]+[0]*(n-1)for _ in range(m-1) 组成m行,n-1列
# [[1]*n]+[[1]+[0]*(n-1)for _ in range(m-1)]组成m行,n列
a = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
for i in range(1, m):
for j in range(1, n):
a[i][j] = a[i - 1][j] + a[i][j - 1]
return a[m - 1][n - 1]
