问题描述
该题是来自力扣的一道题目，题目如下；
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
| s[a][b]=s[a-1][b]+s[a][b-1] |
|---|
该关系式表示：要到达坐标(a,b)则是由到到(a-1,b)与(a,b-1)的所有路径之和：
1 |
1 |
1 |
1 |
1 |
1 |
|---|---|---|---|---|---|
1 |
|||||
1 |
S[a][b-1] |
||||
1 |
S[a-1][b] |
S[a][b] |
即要到达s[a][b]点必先到达S[a][b-1]或者S[a-1][b]，所以说到达s[a][b]的路径数目就是S[a][b-1]与S[a-1][b]路径之和；同时因为第一行与第一列的路径仅由该行或该列的路径所达到，所以只有一条路径。
代码解决
s = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]#将m,n构成的表转化为二维数组。for x in range(1, m): for y in range(1, n):#遍历表中的各个元素。 s[x][y] = s[x-1][y] + s[x][y-1]#满足的关系式print(s[-1][-1])#输出 |
|---|
