【题目】

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

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

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

示例 1：

示例 1.png

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

【题目解析】

解题方法

采用动态规划的思路，定义dp[i][j]为到达(i, j)位置的不同路径的总数，那么可以得出状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]，即到达某个格子的路径数等于它上方格子的路径数加上它左方格子的路径数。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化一个m*n的二维数组，所有值为1。第一行和第一列的路径数为1，因为它们只能一直往下或往右。
        dp = [[1]*n for _ in range(m)]
        # 从(1, 1)开始遍历，因为(0, 0)为起始点，已经初始化。
        for i in range(1, m):
            for j in range(1, n):
                # 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
                # 当前点的路径数 = 从上方来的路径数 + 从左方来的路径数
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # 返回右下角点的路径数
        return dp[-1][-1]

执行效率

image.png

【总结】

适用问题类型

动态规划算法适用于多种类型的问题，尤其是那些可以被分解为重叠子问题的计数问题、最值问题、最优解问题等。"不同路径"问题是一个经典的计数问题，要求计算从网格的左上角到右下角的所有可能路径数量。

解决算法：动态规划

• 算法特点：动态规划算法的核心特点在于解决了重叠子问题，通过构建DP表（通常是一维或二维数组）来保存子问题的解，避免了重复计算。同时，DP算法能够提供一种系统的求解框架，明确地定义状态、状态转移方程以及初始状态和边界条件。

• 时间复杂度与空间复杂度：

  • 时间复杂度为O(m*n)，其中m和n分别代表网格的行数和列数。这是因为需要遍历整个网格一次，对每个格子计算到达它的路径数量。
  • 空间复杂度为O(m*n)，主要空间开销来源于DP表的大小。在一些特殊情况下，通过状态压缩技巧可以将空间复杂度优化到O(n)或O(m)。

实践意义

动态规划算法在实践中有着广泛的应用，能够有效解决包括但不限于路径计数、字符串处理、背包问题等多种类型的问题。掌握动态规划不仅能够帮助我们解决特定的算法题目，更能够在面对实际编程和软件开发中的复杂问题时，提供一种高效且系统的解决方案。学习和应用动态规划，对于提升个人的问题解决能力和编程能力都有显著的帮助。

综上所述，动态规划作为一种强大的算法设计方法论，对于解决"不同路径"这类问题具有明显的优势，它通过优化计算过程、减少不必要的计算，不仅提高了算法的执行效率，还增强了算法对于复杂问题的处理能力。

题目链接

不同路径