问题描述
该题是来自力扣的一道题目，题目如下；
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
解决方案
拿到该题，第一步想到的是利用for循环暴力法来决解，可能会超时，所以考虑到动态规划。
思路如下：
将路径的数目设为：s[a][b],(a,b则分别代表表格中的坐标)因为题目规定只能向下或者向右移动，所以可以得到一个关系式：
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])#输出 |
