动态规划路径问题解析：最小路径和与地下城游戏

1. 动态规划路径问题实战：从最小路径和到地下城游戏

动态规划（Dynamic Programming）作为算法领域的核心思想，在各类编程面试和实际工程问题中频繁出现。路径问题因其直观性和递推特性，成为理解动态规划的最佳切入点。今天我们就来深度剖析两个经典题目：最小路径和（LeetCode 64）和地下城游戏（LeetCode 174），通过对比分析揭示动态规划的状态定义艺术。

提示：本文假设读者已掌握动态规划基础概念，若需前置知识可参考《动态规划五步法》系列文章

1.1 最小路径和问题描述

给定一个包含非负整数的 m x n 网格，每次只能向下或向右移动一步，找到从左上角到右下角的最小路径和。例如：

code复制[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

最小路径和为 7（1→3→1→1→1）

1.2 地下城游戏问题描述

一个恶魔抓住了公主并囚禁在地牢的右下角，骑士从左上角出发，每次只能向右或向下移动。地牢用二维数组表示，正数增加骑士健康值，负数则减少。骑士初始至少需要多少健康值才能成功救出公主？例如：

code复制[
  [-2,-3,3],
  [-5,-10,1],
  [10,30,-5]
]

初始至少需要 7 点健康值

2. 最小路径和的标准解法

2.1 状态定义与转移方程

定义 dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。状态转移方程：

code复制dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

边界条件：

• 第一行：只能从左向右
• 第一列：只能从上向下

2.2 空间优化技巧

由于每次只用到上一行和当前行数据，可将空间复杂度从 O(mn) 优化到 O(n)：

python复制def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = grid[0][0]
    
    # 初始化第一行
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]
    
    for