多维动态规划题解——最小路径和【LeetCode】空间优化一维数组
一、算法逻辑（逐步思路）
❓ 题目描述：
给定一个 m × n 的非负整数网格 grid，从左上角出发，只能向右或向下走，求走到右下角的路径中，路径权值之和最小是多少。
✅ 解题思路（动态规划 + 一维滚动数组）
1. 状态定义：
- 定义一维数组
f[j+1]表示当前处理行中，到达第j列位置的最小路径和； - 数组长度为
n + 1，其中f[0]永远不会使用，目的是简化边界处理。
2. 初始化：
f = [inf] * (n + 1)
f[1] = 0- 初始化第一行前的“虚拟入口”为
0，使得第一个格子grid[0][0]可以自然转移； - 其余设为
inf，保证转移时不会取到非法路径。
3. 状态转移：
f[j + 1] = min(f[j], f[j + 1]) + xf[j]是左边来的；f[j + 1]是上边来的（因为当前是新一行，但数组中仍是旧值）；x是当前格子grid[i][j]的值；- 取这两个来源的最小路径，加上当前值，更新当前位置的路径和。
4. 返回结果：
- 走到最右下角
grid[m-1][n-1]，对应一维数组的f[n]。
二、算法核心点
✅ 核心思想：二维动态规划的空间优化
- 每个格子只依赖它左边和上边的状态，因此一行一行滚动更新就足够；
- 使用一维数组
f来记录当前行的最小路径和，循环内覆盖更新； - 边界偏移技巧使得代码无需特判第一行第一列。
class Solution:def minPathSum(self, grid: List[List[int]]) -> int:n = len(grid[0])f = [inf] * (len(grid[0]) + 1)f[1] = 0for row in grid:for j, x in enumerate(row):f[j + 1] = min(f[j], f[j + 1]) + xreturn f[n]三、复杂度分析
- 时间复杂度：O(m × n)
- 每个格子访问一次。
- 空间复杂度：O(n)
- 只需要一个一维数组长度为
n+1。
- 只需要一个一维数组长度为
总结表
维度 | 内容 |
✅ 思路逻辑 | 一维数组滚动更新当前行，取左/上最小路径和 + 当前值 |
✅ 核心技巧 | 空间优化 + 偏移一位避免边界判断 |
✅ 时间复杂度 | O(m × n) |
✅ 空间复杂度 | O(n) |
✅ 举例说明
grid = [[1, 3, 1],[1, 5, 1],[4, 2, 1]
]- 初始 f:
[inf, 0, inf, inf] - 第一行更新后:
[inf, 1, 4, 5] - 第二行更新后:
[inf, 2, 7, 6] - 第三行更新后:
[inf, 6, 8, 7] - 最终答案为
f[3] = 7
路径为：1 → 3 → 1 → 1 → 1