62.不同路径

dp, math, https://leetcode.cn/problems/unique-paths/

一个机器人位于一个 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^9

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*n for _ in range(m)]
        for i in range(1, m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 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[-1][-1]

这是一个非常经典的动态规划空间优化问题。

我们可以把 “滚动数组” 理解为 “只记录当前行状态，并在计算中覆盖旧状态” 的技巧。

1. 核心逻辑：为什么可以降维？

让我们回头看你提供的 2D 代码中的状态转移方程：

python

dp[i][j] = dp[i-1][j] + dp[i][j-1]

观察这个方程，计算 dp[i][j]（当前格子的路径数）只需要两个值：

dp[i-1][j]：正上方 的格子的路径数。
dp[i][j-1]：左边的格子的路径数。

关键点： 我们根本不需要第 i-2 行、第 i-3 行的数据。我们在计算第 i 行时，只需要第 i-1 行的数据。

一旦第 i 行的某个格子计算完毕，它正上方的那个数据（第 i-1 行的旧数据）就再也没用了。因此，我们可以直接用由一个 一维数组 来不断刷新（滚动）状态。

2. 它是如何滚动的？

假设 m=3, n=3。我们只用一个长度为 n 的一维数组 dp。

初始化： 第一行全是 1（因为一直向右走只有一种方法）。 dp = [1, 1, 1]

开始遍历行（i = 1 到 m-1）：

我们现在要计算第二行的数据，直接在 dp 数组上修改。公式变为： dp[j] = dp[j] + dp[j-1]

这里的含义是：

等号右边的 dp[j]：还没有被更新，它存的是 上一行 (i-1) 同列的值（即 从上方来 的路径）。
等号右边的 dp[j-1]：刚刚被更新过，它存的是 当前行 (i) 前一列的值（即 从左方来 的路径）。
等号左边的 dp[j]：更新后的值，变成了当前行的值。

3. 代码实现

将原本的 O(m * n) 空间复杂度降低为 O(n)。

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 1. 初始化滚动数组
        # 相当于二维 DP 的第一行，全是 1
        dp = [1] * n
        
        # 2. 从第二行开始遍历 (i 从 1 到 m-1)
        for i in range(1, m):
            # 3. 从第二列开始更新每一格 (j 从 1 到 n-1)
            # 第 0 列永远是 1，不需要更新，所以从 1 开始
            for j in range(1, n):
                # 核心方程：
                # dp[j] (新) = dp[j] (旧，即上面的值) + dp[j-1] (新，即左面的值)
                dp[j] += dp[j-1]
        
        # 4. 返回右下角的值
        return dp[-1]

4. 进一步优化（锦上添花）

虽然空间复杂度已经是线性的了，但在极端的 m 和 n 差异下还可以微调。比如 m = 10000, n = 2。如果我们按上面的代码建立数组，长度是 2。但如果 m = 2, n = 10000，数组长度就是 10000。

由于网格翻转（行变列，列变行）路径数不变，我们可以取 m 和 n 中较小的那个作为数组长度，从而保证空间复杂度是 O(min(m, n))。

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 确保 n 是较小的那个数，用它来做列数以节省空间
        if m < n:
            m, n = n, m
            
        dp = [1] * n
        
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
                
        return dp[-1]

总结

理解：把二维表格压扁成一行。
公式：dp[j] += dp[j-1]。
含义：自己 = 自己(上) + 左边。
优点：省去了存储整个矩阵的空间，只存储一行。

dfs, dp都可以实现，但是dfs在m=23,n=12超时，dp数组初始化需要想明白。

将 cnt 作为类的属性来管理，或者将 cnt 作为参数传递给 dfs 函数。这里我们选择将 cnt 作为类的属性来管理，这样可以保持代码的清晰和简洁。 self.cnt = 0 不需要写在 uniquePaths 函数的内部，可以在类的初始化方法 __init__ 中进行初始化。这样做可以确保每次创建新的 Solution 实例时，cnt 都会被重置为 0。

python

# dfs 超时
class Solution:
    def __init__(self):
        self.cnt = 0

    def uniquePaths(self, m: int, n: int) -> int:
        dx = [0, 1]
        dy = [1, 0]
        visited = [[False] * n for _ in range(m)]

        def dfs(x, y):
            if x == m - 1 and y == n - 1:
                self.cnt += 1
                return
            visited[x][y] = True
            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    dfs(nx, ny)
            visited[x][y] = False

        dfs(0, 0)
        return self.cnt

# 示例用法
if __name__ == "__main__":
    sol = Solution()
    m = 3
    n = 7
    print(sol.uniquePaths(m, n))

因为纯dfs超时，考虑使用lru_cache。

使用 lru_cache 时需要注意一些细节，特别是当涉及到类方法和状态共享时。在上面的代码中，lru_cache 缓存的是 dfs 函数的结果，但是 dfs 函数内部修改了类的状态（即 self.cnt），这会导致缓存的行为不符合预期。
具体来说，lru_cache 会缓存 dfs 函数的返回值，而不是函数执行过程中的副作用（如修改 self.cnt）。因此，当 dfs 函数被多次调用时，self.cnt 的值可能不会按预期增加。
为了解决这个问题，可以考虑以下方法：使用 lru_cache 但不依赖类状态
通过将 cnt 作为返回值传递，避免了类状态的影响，同时利用 lru_cache 提高了性能。

python

from functools import lru_cache

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dx = [0, 1]
        dy = [1, 0]

        @lru_cache(maxsize=None)
        def dfs(x, y):
            if x == m - 1 and y == n - 1:
                return 1
            cnt = 0
            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < m and 0 <= ny < n:
                    cnt += dfs(nx, ny)
            return cnt

        return dfs(0, 0)

# 示例用法
if __name__ == "__main__":
    sol = Solution()
    m = 3
    n = 7
    print(sol.uniquePaths(m, n))

使用深度优先搜索（DFS）来解决这个问题效率不高，特别是当网格很大时。这个问题可以通过动态规划（Dynamic Programming, DP）来更高效地解决。动态规划可以避免重复计算，并且时间复杂度为 O(m*n)。

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 创建一个二维数组 dp 来存储到达每个位置的路径数
        dp = [[1] * n for _ in range(m)]
        
        # 动态规划填表
        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[-1][-1]

#m, n = map(int, input().split())

# 创建解决方案实例并调用方法
#solution = Solution()
#ans = solution.uniquePaths(m, n)

#print(ans)

使用动态规划来计算从左上角到右下角的不同路径数。我们创建了一个 dp 数组，其中 dp[i][j] 表示到达 (i, j) 位置的路径数。初始化时，所有第一行和第一列的值都设为 1，因为从起点到这些位置只有唯一的一条路径。然后，对于其他每个位置 (i, j)，其路径数等于从上方和左侧到达该位置的路径数之和。最后返回 dp[m-1][n-1] 即为所求的答案。

math思路

从左上角到右下角的过程中，我们需要移动 m+n−2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，即组合数：

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        import math   
        result = math.comb(m+n-2,m-1)
        return result

思路：选择用Iru_cache的方法加上递归就可以轻松完成（耗时10min)

python

# 胡家豪 24元培学院
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def roads(m,n):
            if m==1 or n==1:
                return 1
            else:
                return roads(m-1,n)+roads(m,n-1)
        return roads(m,n)

62.不同路径 ​

62.不同路径