本文通过剖析leetcode 45题“跳跃游戏ii”的典型解法，系统阐述贪心算法的核心判据：局部最优选择的无后效性、无需回溯的单次决策性，以及与动态规划的本质区别。
本文通过剖析leetcode 45题“跳跃游戏ii”的典型解法，系统阐述贪心算法的核心判据：局部最优选择的无后效性、无需回溯的单次决策性，以及与动态规划的本质区别。
在算法设计中，“贪心”常被误用为“每次选看起来最好的”，但严谨的判定需回归其理论本质。一个算法要被认定为贪心算法，必须同时满足以下三项核心准则：
- 局部最优驱动全局最优：每一步决策仅基于当前状态，选择当前看来最优的选项（如最大覆盖范围、最小代价等），且该选择不依赖未来子问题的求解结果；
- 无后效性与不可撤销性：一旦做出选择，便不再更改；后续步骤不会回溯或修正此前决策；
- 无需穷举所有可能路径：不依赖对多个候选分支的完整枚举与比较，而是通过明确策略（如“跳到能抵达最远位置的下一步”）直接确定唯一行动。
反观提问中提供的Python实现：
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]该解法不符合贪心算法定义，原因如下：
- ✅ 它确实在追求“全局最优”（最小跳跃次数）；
- ❌ 但它严重依赖子问题的完整求解：每个 nums[i] 的值，是通过穷举所有可达位置 i+a 并比较其已计算出的 nums[i+a] 值后取最小值得到的；
- ❌ 决策过程具有强回溯依赖性：nums[i] 的计算必须等待 nums[i+1..i+nums[i]] 全部就绪；
- ❌ 没有采用单一启发式策略（如“跳到当前覆盖范围内能延伸最远的索引”），而是进行O(nums[i])级的内层循环枚举——这是典型动态规划（DP）的“状态转移”特征。
真正符合贪心范式的解法应具备线性扫描 + 边界维护结构。例如本题的标准贪心解法：
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；
- 当遍历至当前跳跃的边界 current_end 时，强制执行一次跳跃（jumps++），并将新边界设为迄今所能达到的最远位置 farthest；
- 不回看、不枚举、不缓存所有子问题解——仅凭一次正向扫描和局部极值更新，即完成全局最优构造。
⚠️ 注意事项：
- 贪心的正确性往往需要数学证明（如交换论证、拟阵性质），不能仅凭直觉；
- 动态规划强调“自底向上/自顶向下”的子问题复用，贪心则强调“自左向右”的即时决策；
- 若某算法需 min() / max() 遍历多个候选并择优，大概率属于DP；若仅用 if 或 max() 更新单个指标并立即推进，则更接近贪心。
综上，判断算法是否贪心，关键不在“是否追求最优”，而在于决策机制是否摒弃穷举、拒绝回溯、依赖即时局部信息直接定策。掌握这一分水岭，才能避免将DP误标为贪心，也为设计新算法提供坚实的范式基础。
