多维动态规划题解——不同路径【LeetCode】递推写法&空间优化

62. 不同路径

基础记忆化搜索写法请参考之前的文章，链接如下

多维动态规划题解——不同路径【LeetCode】记忆化搜索-CSDN博客

基础递推写法实现

此处是基于之前的记忆化搜索写法进行对应翻译得到的

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

空间优化

一、算法逻辑（逐步思路）

❓ 题目简介

• 给定一个大小为 m x n 的网格（左上角为起点，右下角为终点），机器人每次只能向右或向下移动一步，问：从左上角走到右下角，有多少条不同的路径？

✅ 思路解析（DP + 空间优化）

1. 定义状态：

• 使用一维数组 f[j] 表示当前行中，到达第 j 列所需要的路径数量；
• 为什么一维就够？因为第 i 行的路径数只依赖于上一行和当前行左侧的位置。

2. 初始化：

f = [0] * (n + 1)
f[1] = 1

• f[1] = 1 表示第一行第一列的路径数量为 1；
• 注意，这里将索引偏移一位（f[1] 对应网格中第 0 列），是为了简化边界处理（避免 j-1 越界）。

3. 状态转移：

for _ in range(m):
    for j in range(n):
        f[j + 1] += f[j]

• 外层循环跑 m 行；
• 内层循环中，f[j+1] += f[j] 意思是：从左边 j 位置可以走到 j+1 位置；
• 相当于：

• • f[j+1] = 上一轮的 f[j+1]（来自上方） + 当前轮的 f[j]（来自左边）

4. 返回结果：

• f[n] 就是最终到达右下角所需的路径数。

二、算法核心点

✅ 核心思想：二维路径 DP 的一维数组压缩版

• 将 dp[i][j] = dp[i-1][j] + dp[i][j-1] 压缩为一维数组；
• 每次只保留一行数据，在原数组上进行就地更新；
• 本质是从左到右不断累加路径数。

三、复杂度分析

• 时间复杂度：O(m × n)

• • 遍历每个格子一次，共 m 行 n 列。

• 空间复杂度：O(n)

• • 使用一维数组保存状态。

总结表：

🔍 补充说明（偏移技巧）：

• 为什么用 f[1] = 1 而不是 f[0] = 1？

• • 因为循环中我们用的是 f[j+1] 和 f[j]，偏移一位可避免对边界做特殊处理；
  • 这样初始化只需设定一个值，逻辑更简洁。