【原】Python|利用动态规划解决路径数目问题

问题描述

该题是来自力扣的一道题目，题目如下；

一个机器人位于一个 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])#输出

END

主  编   |   王文星

责  编   |   W Z Y

 where2go 团队

---

微信号：算法与编程之美