LeetCode 64. Minimum Path Sum 题解
LeetCode 64. Minimum Path Sum 题解
题目描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12解题思路
这是一个经典的动态规划问题，与 Unique Paths 类似，但要求最小路径和。
状态定义：
- dp[i][j] 表示从起点到达位置 (i, j) 的最小路径和
状态转移方程：
- 只能从上方或左方到达
- dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
初始条件：
- dp[0][0] = grid[0][0]
- 第一行：dp[0][j] = dp[0][j-1] + grid[0][j]
- 第一列：dp[i][0] = dp[i-1][0] + grid[i][0]
代码实现
方法一：二维动态规划
def minPathSum(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 填充 dp 数组 for i in range(1, m): for j in range(1, n): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]方法二：一维动态规划（空间优化）
def minPathSum(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [0] * n for i in range(m): for j in range(n): if i == 0 and j == 0: dp[j] = grid[i][j] elif i == 0: dp[j] = dp[j-1] + grid[i][j] elif j == 0: dp[j] = dp[j] + grid[i][j] else: dp[j] = grid[i][j] + min(dp[j], dp[j-1]) return dp[n-1]复杂度分析
- 时间复杂度：O(m × n)，需要遍历整个网格
- 空间复杂度：
- 方法一：O(m × n)
- 方法二：O(n)
测试案例
# 测试案例 1 assert minPathSum([[1,3,1],[1,5,1],[4,2,1]]) == 7 # 测试案例 2 assert minPathSum([[1,2,3],[4,5,6]]) == 12 # 测试案例 3 assert minPathSum([[1]]) == 1 # 测试案例 4 assert minPathSum([[1,2],[1,1]]) == 3总结
本题是动态规划的经典应用，与 Unique Paths 类似但增加了路径权重的考虑。
关键点：
- 状态定义：dp[i][j] 表示到达 (i, j) 的最小路径和
- 状态转移：只能从上方或左方到达，取两者中的最小值
- 空间优化：可以降维，只保留上一行的数据
通过本题可以深入理解带权路径的动态规划问题。