LeetCode每日一题: 62. 不同路径

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角.

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
   示例 2:
   输入: m = 7, n = 3
   输出: 28

思路

1. 这个题是经典的动态规划题, 采用动态规划的思想即可
2. 我们先找到结束条件: 结束的条件是要走到右下角格子, 结束的前一步只能是在右下角上边或者左边的一个格子
3. 再找到状态转移公式: 从结束条件可以推导出f(i, j) = f(i-1, j) + f(i, j-1)
4. 确定边界条件, 用于获得初始值: 在第0行和第0列时, 只有1种走法
5. 确定求解顺序: 从左上角出发, 往右或者往下走, 直到右下角
6. 有了初始值、状态转移公式、求解顺序, 就可以得出路径的走法数量

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]