本文通过分析 leetcode 45 题“跳跃游戏 ii”的一种常见实现，阐明贪心算法的核心判据：是否在每一步都基于局部最优选择、无需回溯或全局比较即可构造全局最优解；并指出该解法实为动态规划，而非贪心算法。
本文通过分析 leetcode 45 题“跳跃游戏 ii”的一种常见实现，阐明贪心算法的核心判据：是否在每一步都基于局部最优选择、无需回溯或全局比较即可构造全局最优解；并指出该解法实为动态规划，而非贪心算法。
在算法设计中，“贪心”并非指“看起来很高效”或“每次都选最小/最大”，而是一种具有严格结构特征的范式。一个算法要被明确认定为贪心算法，必须同时满足以下三个关键条件：
- 贪心选择性质（Greedy Choice Property）：在每一步决策中，仅依据当前状态做出局部最优选择，且该选择一旦确定便永不撤销；
- 最优子结构性质（Optimal Substructure）：问题的全局最优解包含其子问题的最优解；
- 无后效性 + 无回溯需求：后续决策不依赖于此前未被选中的候选解，也无需枚举、比较所有可能路径。
我们以提问者提供的跳跃游戏 II 解法为例进行剖析：
def jump(nums):
n = len(nums)
# 自底向上 DP：dp[i] 表示从索引 i 到达末尾的最少跳跃次数
dp = [float('inf')] * n
dp[n-1] = 0 # 终点无需跳跃
for i in range(n-2, -1, -1): # 从倒数第二位向前遍历
if nums[i] == 0:
continue # 无法从该位置出发
# 枚举所有可达的下一步位置
for j in range(1, nums[i] + 1):
if i + j < n and dp[i + j] != float('inf'):
dp[i] = min(dp[i], dp[i + j] + 1)
return dp[0]这段代码本质上是自底向上的动态规划：
- 它将原问题分解为 n 个子问题（每个 dp[i] 对应“从位置 i 到终点的最少跳数”）；
- 每次计算 dp[i] 时，穷举所有合法跳跃步长 j ∈ [1, nums[i]]，查看所有可达的 i+j 位置，并取其中 dp[i+j] + 1 的最小值；
- 这一过程显式依赖对多个候选解的比较与取优，而非依据某个简单规则（如“跳得最远”）直接选定唯一动作。
✅ 这正是动态规划的典型特征：状态转移需遍历所有可行决策分支，保留最优子结构结果。
❌ 而贪心算法在此题中的正确解法（如经典 BFS 层序或“覆盖范围扩展”法）则完全不同：
def jump_greedy(nums):
if len(nums) <= 1:
return 0
jumps = 0
cur_end = 0 # 当前跳跃能到达的最远索引
farthest = 0 # 下一跳可覆盖的最远索引
for i in range(len(nums) - 1): # 不处理最后一个位置
farthest = max(farthest, i + nums[i])
if i == cur_end: # 必须进行一次跳跃才能继续前进
jumps += 1
cur_end = farthest
if cur_end >= len(nums) - 1:
break
return jumps该贪心解法的关键在于：
- 每一步不比较所有路径，而是维护“当前跳跃能覆盖的右边界”和“下一跳可扩展的最大边界”；
- 当遍历到当前跳跃的右边界 cur_end 时，立即执行一次跳跃（jumps++），并将 cur_end 更新为已知最远可达位置 farthest；
- 决策依据是单一启发式规则：“在当前覆盖范围内，选择能使下次跳跃尽可能远的位置”，无需回看、无需枚举、不可逆。
? 因此，判断一个算法是否为贪心，核心在于审视其决策机制：
- 若算法在每一步都仅依据当前信息，用确定性规则选出唯一动作，且该动作被证明能保持全局最优性 → 是贪心；
- 若算法在每一步都枚举所有可行选项、比较并取最优（尤其当选项数量随输入增长而变化）→ 本质是动态规划或暴力搜索；
- 即使目标是“找最小/最大”，也不代表算法是贪心——DP 同样追求最优，但路径不同。
⚠️ 注意事项：
- 贪心算法的正确性必须严格证明（通常用交换论证或归纳法），不能仅凭直觉；
- 很多问题存在贪心解法，但并非所有最优解法都是贪心；同一问题的不同解法可能分属不同范式；
- 提问者代码修改了输入数组 nums 存储状态，虽功能等价，但破坏了函数纯度与可读性，实践中应使用独立 dp 数组。
总结而言，贪心是一种“目光聚焦当下、决策果决自信”的策略；而动态规划则是“回溯历史、权衡所有可能”的审慎风格。理解二者的分水岭，不在于输出结果是否最优，而在于每一步是如何抵达最优的。
