What is the most efficient way to solve the Unique Paths problem?

The most efficient way is using dynamic programming with a 1D array to optimize space complexity while preserving time efficiency. This reduces space usage to O(n).

How can combinatorics be used to solve the Unique Paths problem?

Combinatorics can be used by calculating the number of ways to arrange the required down and right movements in a sequence of total steps using the binomial coefficient formula.

What is the time complexity of the dynamic programming solution?

The time complexity of the dynamic programming solution is O(m*n), where m and n are the grid dimensions.

Can the grid dimensions be larger than 100?

No, the problem constraints ensure that the grid dimensions m and n will always be between 1 and 100.

What is the binomial coefficient formula used for in this problem?

The binomial coefficient formula is used to calculate the number of ways to choose the down or right movements from the total steps, which determines the number of unique paths.

#62

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不同路径

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

数学动态规划组合数学

题目描述

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

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

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

示例 1：

输入：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⁹

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示从左上角走到 $(i, j)$ 的路径数量，初始时 $f[0][0] = 1$ ，答案为 $f[m - 1][n - 1]$ 。

考虑 $f[i][j]$ ：

如果 $i \gt 0$ ，那么 $f[i][j]$ 可以从 $f[i - 1][j]$ 走一步到达，因此 $f[i][j] = f[i][j] + f[i - 1][j]$ ；
如果 $j \gt 0$ ，那么 $f[i][j]$ 可以从 $f[i][j - 1]$ 走一步到达，因此 $f[i][j] = f[i][j] + f[i][j - 1]$ 。

因此，我们有如下的状态转移方程：

f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i - 1][j] + f[i][j - 1] & \textit{otherwise} \end{cases}

最终的答案即为 $f[m - 1][n - 1]$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

我们注意到 $f[i][j]$ 仅与 $f[i - 1][j]$ 和 $f[i][j - 1]$ 有关，因此我们优化掉第一维空间，仅保留第二维空间，得到时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$ 的实现。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests whether the candidate understands combinatorics and dynamic programming.
question_mark
Evaluates the ability to optimize space complexity in dynamic programming solutions.
question_mark
Assesses familiarity with efficient solution strategies for grid-based problems.

warning

常见陷阱

外企场景

error
Forgetting to initialize the first row and column of the dynamic programming table.
error
Misunderstanding the combinatorics formula for calculating the number of paths.
error
Using an inefficient solution with excessive space complexity when an optimized approach is possible.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modified problem where the robot can move in more directions (e.g., up, left, right, down).
arrow_right_alt
Unique paths problem with obstacles in the grid, requiring pathfinding around blocked cells.
arrow_right_alt
Grid size variation with constraints on maximum m or n values for more challenging scenarios.

help

常见问题

外企场景

继续练习

#458 可怜的小猪 #920 播放列表的数量 #70 爬楼梯