62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角.
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
思路
- 这个题是经典的动态规划题, 采用动态规划的思想即可
- 我们先找到结束条件: 结束的条件是要走到右下角格子, 结束的前一步只能是在右下角上边或者左边的一个格子
- 再找到状态转移公式: 从结束条件可以推导出f(i, j) = f(i-1, j) + f(i, j-1)
- 确定边界条件, 用于获得初始值: 在第0行和第0列时, 只有1种走法
- 确定求解顺序: 从左上角出发, 往右或者往下走, 直到右下角
- 有了初始值、状态转移公式、求解顺序, 就可以得出路径的走法数量
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
lst = [[False]*m]*n
for i in range(n):
for j in range(m):
if i == 0 or j==0:
lst[i][j] = 1
else:
lst[i][j] = lst[i-1][j] + lst[i][j-1]
return lst[n-1][m-1]
