网格中的不同路径与最小路径和
为有障碍物和无障碍物的不同路径问题填充二维 DP 表，然后改进方法以最小化路径上的值之和。
网格中的不同路径与最小路径和 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
网格上的不同路径
不同路径（LeetCode 62）的问题是：在一个 m×n 的网格中，如果只能向右或向下移动，从左上角到右下角有多少条不同路径？对于一个 3×7 的网格，答案是 28。关键洞察是，到达单元格 (i,j) 的每条路径都必须来自 (i-1,j)（上方）或 (i,j-1)（左侧），因此可以自然地建立二维 DP 公式。
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2不同路径的二维 DP 表
定义 dp[i][j] 表示到达单元格 (i,j) 的路径数。第一行和第一列全部为 1（到达顶行或最左列中的任意单元格都只有一种方法）。对于其他单元格：dp[i][j] = dp[i-1][j] + dp[i][j-1]。逐行填充表格，答案就是 dp[m-1][n-1]。时间复杂度为 O(m×n)，空间复杂度为 O(m×n)，还可以降为 O(n)。
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
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[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)将空间优化到 O(n)
由于 dp[i][j] 只依赖当前行和上一行，因此可以用一个一维数组替代完整的二维表格。先将所有值初始化为 1，然后逐行进行原地更新：dp[j] += dp[j-1]。处理完第 i 行后，dp[j] 保存的就是二维表格中 dp[i][j] 的值。这是二维 DP 问题中常见的优化模式。
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28不同路径 II：障碍物
不同路径 II（LeetCode 63）在网格中加入了障碍物（标记为 1 的单元格）。任何经过障碍物的路径都无效，因此如果 obstacle[i][j] == 1，则 dp[i][j] = 0。否则，递推式不变：dp[i][j] = dp[i-1][j] + dp[i][j-1]。如果起点或终点被阻塞，答案立即为 0。请仔细初始化初始条件——一旦第一行或第一列出现 1，该行或该列后续的所有单元格都应为 0。
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2最小路径和问题
最小路径和（LeetCode 64）的问题是：给定一个由非负整数填充的 m×n 网格，找出一条从左上角到右下角的路径，使路径上所有数字之和最小（只能向右或向下移动）。例如，在 [[1,3,1],[1,5,1],[4,2,1]] 中，路径 1→3→1→1→1 的总和为 7。其 DP 状态与不同路径相同，但递推式使用最小值而不是加法。
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)最小路径和的 DP 实现
定义 dp[i][j] 表示到达单元格 (i,j) 的最小代价。初始条件：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]（只能从上方到达）。一般情况：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。这直接体现了最优性原理。
def min_path_sum(grid):
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): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
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]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7原地计算最小路径和
如果允许修改输入网格，您可以对其进行原地更新，从而无需分配单独的 DP 表格。除了输入本身之外，这会将辅助空间降为 O(1)。面试官有时会询问这种优化——在执行前，请先确认是否允许修改输入。如果不允许，使用一维滚动数组技巧可以在不修改输入的情况下将空间复杂度降为 O(n)。
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7三角形最小路径和
三角形（LeetCode 120）要求计算三角形数组中从顶部到底部的最小路径和，其中每一步都要移动到下一行相邻的数字。自底向上的 DP 最为简洁：从倒数第二行开始，对每个单元格加上其正下方两个单元格中的较小值。这样无需跟踪起始下标，答案也会自然地逐层汇聚到顶点。
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)地下城中的网格 DP
地下城游戏（LeetCode 174）的问题是：在一个包含负数（伤害）和正数（治疗）单元格的网格中，计算救出右下角公主所需的最小初始生命值。您必须向右或向下移动。关键是反向填充 DP 表格（从右下角到左上角），计算到达每个单元格时所需的最小生命值。对于每个单元格：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。生命值必须始终至少为 1。
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7网格 DP 问题对比
网格 DP 问题具有相同的结构，但在填充方向和转移运算上有所不同：不同路径使用加法（统计所有方法）。最小路径和使用最小值（进行优化）。地下城游戏反向填充（计算从后续位置开始所需的生命值）。处理新的网格 DP 问题时，请问自己：(1) 每个单元格表示什么？(2) 应该以哪个方向填充？(3) 使用什么运算组合相邻单元格？回答这三个问题，就能确定完整的解法。
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')网格 DP 的复杂度总结
这里的所有网格 DP 问题都需要O(m×n) 的时间。空间复杂度从完整表格的O(m×n)，到使用一维滚动数组时的O(n)，再到可以原地修改网格时的O(1) 辅助空间。在面试中，请先给出 O(m×n) 的解法，再说明 O(n) 的空间优化——这能体现您对权衡的理解。对于所有问题，还应考虑是否存在贪心捷径（例如不同路径的数学公式）。
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：不同路径使用 dp[i][j] = dp[i-1][j] + dp[i][j-1] 填充二维表格，并且可以通过组合数学在 O(1) 空间内计算；最小路径和使用相同的结构，但将加法替换为 min，以求得最优路径代价；以及所有网格 DP 问题都遵循这样的模式：为每个单元格定义一个状态，并选择一种转移运算（sum、min、max）。接下来，我们将使用二维 DP 研究两个序列的最长公共子序列。
常见问题解答
「网格中的不同路径与最小路径和」课时是免费的吗？
是的 — 「网格中的不同路径与最小路径和」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「网格中的不同路径与最小路径和」这节课中我会学到什么？
为有障碍物和无障碍物的不同路径问题填充二维 DP 表，然后改进方法以最小化路径上的值之和。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「网格中的不同路径与最小路径和」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 网格中的不同路径与最小路径和
- 最长公共子序列
- 编辑距离（Levenshtein）
- 二维 DP 的空间优化