本文通过 LeetCode 跳跃游戏 II（Jump Game II）的经典解法对比，系统阐述贪心算法的核心判据：是否在每一步都仅依据当前局部最优决策、不回溯、不依赖全局子问题解，并指出动态规划解法虽追求“最优”，但因遍历所有可行转移而本质不同。
本文通过 leetcode 跳跃游戏 ii（jump game ii）的经典解法对比，系统阐述贪心算法的核心判据：是否在每一步都**仅依据当前局部最优决策、不回溯、不依赖全局子问题解**，并指出动态规划解法虽追求“最优”，但因遍历所有可行转移而本质不同。
判断一个算法是否为贪心算法，不能仅凭“它在找最优解”或“每步选最好的”这类模糊印象，而需严格考察其决策机制与结构特征。核心判据有三，缺一不可：
✅ 局部最优即刻决定：在每个决策点，算法基于当前状态（无需未来信息或全局视图），直接选择一个明确、确定的“最好”选项；
✅ 无回溯、无枚举：不尝试多种可能路径，不比较多个候选动作的后续影响，更不保存/复用子问题解；
✅ 单向推进、不可撤销：决策一旦做出即固化，后续步骤完全基于该决策结果展开，不修正、不重算先前位置。
我们以你提供的跳跃游戏 II 解法为例深入分析：
# 你的解法（自底向上动态规划）
for i in range(len(nums) - 1, -1, -1):
if i == len(nums) - 1:
nums[i] = 0
continue
if nums[i] == 0:
nums[i] = None
continue
curMinStep = float('inf')
for a in range(nums[i], 0, -1): # ← 关键：穷举所有可能跳跃步长！
if i + a >= len(nums):
continue
nextStop = nums[i + a]
if nextStop is None:
continue
curMinStep = min(curMinStep, nextStop + 1) # ← 关键：依赖已计算的子问题解
nums[i] = curMinStep
return nums[0]这段代码不是贪心算法，而是典型的自底向上的动态规划（DP），原因如下：
- ? 它在枚举而非选择：内层 for a in range(nums[i], 0, -1) 显式遍历了从位置 i 出发的所有合法跳跃距离（1 到 nums[i]），逐一验证 i+a 位置的已知最优解，再取最小值。这本质上是状态转移的穷举计算，而非“一眼选定最佳动作”。
- ? 它严重依赖子问题解：nums[i] 的值完全由 nums[i+1], nums[i+2], ..., nums[i+nums[i]] 这些已被求解的子问题决定。这是 DP 的标志性特征（最优子结构 + 重叠子问题），而贪心算法从不缓存或复用此类中间结果。
- ? 它不具备贪心的“短视性”：贪心策略在此题中的典型体现是——在当前能到达的最远范围内，选择下一步能跳得最远的那个位置（如标准贪心解法中的 farthest = max(farthest, i + nums[i])）。你的算法却反向扫描、逐个比对，视野覆盖全局可达域，违背了贪心“只看眼前一步最优”的哲学。
✅ 对照真正的贪心解法（O(n) 时间、O(1) 空间）：
def jump(nums):
if len(nums) <= 1:
return 0
jumps = 0
current_end = 0 # 当前跳跃能覆盖的最右边界
farthest = 0 # 在当前覆盖范围内，下一步能跳到的最远位置
for i in range(len(nums) - 1): # 不需处理最后一个位置
farthest = max(farthest, i + nums[i])
if i == current_end: # 必须在此处起跳
jumps += 1
current_end = farthest
if current_end >= len(nums) - 1:
break
return jumps此解法中：
- 每次仅维护两个变量 current_end 和 farthest；
- 在 i == current_end 时强制跳一次，且跳的目标隐含为“在当前覆盖区间内能抵达最远的位置”；
- 不做任何循环枚举，不查表，不递归，不回溯——纯粹基于当前窗口内的局部极值做唯一决策。
? 总结：贪心 ≠ “想选最好的”，而是 “在无可选择的约束下，用最简规则当场拍板”。当你发现自己在代码中写了 for ... in candidates:、min([...])、dp[i] = min(dp[j] + cost) 或需要数组存储历史最优值时，大概率已进入动态规划范畴。真正的贪心，往往简洁得令人惊讶——它不计算“哪个最好”，而是定义“什么就是最好”，然后坚定执行。
掌握这一区分，不仅关乎算法分类，更是理解问题本质与设计高效解法的关键分水岭。
