You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于LeetCode 45自底向上解法是否为贪心算法的疑问

关于LeetCode 45题解法是否为贪心算法的疑问

我在判断算法是否为贪心算法时存在困惑。根据定义,贪心算法通过局部最优选择获取全局最优解,但该定义较宽泛,难以在具体场景判定。此前相关讨论的问题与我的情况不同,故重新提问。

具体场景为LeetCode 45题(跳跃游戏II):给定0索引整数数组nums,初始位置为nums[0],每个元素nums[i]表示从索引i出发的最大向前跳跃长度,要求返回到达最后一个索引的最少跳跃次数(题目保证可到达终点)。

我的Python解法如下:

for i in range(len(nums) - 1, -1, -1):
    if ( i == len(nums) - 1): #take 0 step to reach goal
        nums[i] = 0
        continue
    if (nums[i] == 0):
        nums[i] = None
        continue
        #indicate cannot make any step to reach the goal
    curMinStep = 10000
    for a in range(nums[i], 0, -1):
        #run through all possible number of steps that can be made at current element to find the minimum step toward goal
        if(i + a >= len(nums)): continue
        nextStop = nums[i + a]
        # nextStop: minimum jumps to reach goal from i + a index
        if (nextStop == None ): continue #if nextStop is a 0-steps, means it cannot reach goal
        curMinStep = min(curMinStep, nextStop + 1)
    nums[i] = curMinStep
return nums[0]

解法说明:从数组最后一个索引(终点)向前遍历,将每个位置的值更新为到达终点所需的最少跳跃次数;内层循环遍历当前位置所有可能的跳跃步长,找到能得到最少跳跃次数的选择。

我的疑问:该算法每次都会寻找局部最优解(到达终点的最少跳跃次数),请问它是否属于贪心算法?若不属于,缺少哪些贪心算法的核心特征?


内容的提问来源于stack exchange,提问作者tanLe

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.29 10:52:10