关于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
相关产品推荐
相关产品推荐

