LeetCode 62. 不同路径

题目

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

例：
输入：m = 3, n = 7
输出：28

方法：动态规划

• dp 记录机器人到达该网格的不同路径的数量，初始值均为零
• 因为机器人每次只能向下或向右移动一步，那么机器人到达第一行和第一列的任意位置的路径均只有一条，所以将 dp[i][0] 和 dp[0][i] 赋值 1
• 循环遍历除了第一行和第一列的每个网格。我们通过找规律可知到达每个非第一行和第一列的网格的路径数量均为到达其左边网格的路径数量加上到达其上边网格的路径数量
• 最终返回右下角网格的路径数量

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[0 for col in range(n)] for row in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        for i in range(1, n):
            for j in range(1, m):
                    dp[j][i] = dp[j][i-1] + dp[j-1][i]
        return dp[m-1][n-1]

优化： 因为所有网格的最小路径数量为一，那么初始化时可以从零变成一，从而减少之后的对第一行和第一列的赋值

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[1 for col in range(n)] for row in range(m)]
        for i in range(1, n):
            for j in range(1, m):
                    dp[j][i] = dp[j][i-1] + dp[j-1][i]
        return dp[m-1][n-1]

参考

代码相关：https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html