Q62-不同路径-中等-动态规划

62. 不同路径

Question

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

Example 1:

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

Example 2:

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

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

Example 3:

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

Example 4:

输入：m = 3, n = 3 输出：6

Note:

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

Approach 1: 动态规划

本题目是典型的动态规划问题，因为我们计算到每个格子的路线数目可以通过，之前格子的可到达路线数目计算。具体计算迭代方式如下：

用dp[m][n]记录到达每个位置的路径数目（注意，agent只能右移或者下移）。 考虑边界条件，将dp[0][j]和dp[i][0]单独赋值为1。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = 1
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]


def main():
    m = 7
    n = 3
    solution=Solution().uniquePaths(m,n)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：。

• 空间复杂度：，即为存储所有状态需要的空间。注意到dp[i][j]仅与第i行和第i-1行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换m和n使得 m n，这样空间复杂度降低至 。