64. 最小路径和

题目描述

网格每格是非负代价，只能右/下走，求左上到右下路径上代价之和的最小值。

思路解析

一个格子只能从上或左来，那咱当然挑代价小的那条接上：dp[i][j] = min(上, 左) + grid[i][j]。第一行和第一列只有一条路，前缀累加就行。

第一行/列 · 累加：第一行只能一路向右：1、1+3=4、4+1=5；第一列只能向下：1、1+1=2、2+4=6。都是前缀和。

填 (1,1)：(1,1) 代价 5，从上(4)或左(2)来，挑小的 2：dp = 2 + 5 = 7。

填 (1,2)：(1,2) 代价 1，min(上5, 左7)=5，dp = 5 + 1 = 6。

填 (2,1)：(2,1) 代价 2，min(上7, 左6)=6，dp = 6 + 2 = 8。

右下角：右下角 = min(上6, 左8) + 1 = 7，就是最小路径和。

同一张网格 DP 表，换聚合方式就解不同题：计数用加法、求最小用 min、求最大用 max。

参考代码（Python）

1dp = [[0]*n for _ in range(m)]
2dp[0][0] = grid[0][0]
3for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]   # 第一行
4for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]   # 第一列
5for i in range(1, m):
6    for j in range(1, n):
7        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
8return dp[m-1][n-1]

复杂度分析

• 时间复杂度：O(m×n) —— 每格算一次
• 空间复杂度：O(m×n) —— 可压成一行

套路模板

记住骨架：边界前缀累加、中间 min(上,左)+当前。求最大路径和就把 min 换 max，三角形最小路径和也是它。

1dp[0][0] = grid[0][0]
2# 第一行/列前缀累加
3for i in range(1, m):
4    for j in range(1, n):
5        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
6return dp[m-1][n-1]

易错点

• ❌ 第一行/列也用 min 公式 → ✅ 第一行/列单独前缀累加（它们没有「上」或「左」，硬套会取到不存在的格）
• ❌ 忘了加当前格代价 → ✅ min(上,左) 之后要 + grid[i][j]（路径和要算上当前格）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。