在特定上下文中被视为贪婪算法的标准

Question

我在尝试理解算法是否贪婪时遇到了一些困难。从定义来看，贪婪算法是在局部做出最佳选择以获得全局解决方案的算法。然而，这个定义相当广泛，我不确定在具体情况下如何知道。之前有1篇文章讨论过这个问题，但是问题不同所以我想再问一次。

具体来说，这是问题和算法，我不确定它是否是贪婪的。这是leetcode 45：

给定一个 0 索引的长度为 n 的整数 nums 数组。您最初位于 nums[0]。

每个元素nums[i]代表从索引i向前跳转的最大长度。换句话说，如果你在 nums[i]，你可以跳转到任何 nums[i + j]，其中：

0<= j <= nums[i] and i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以达到 nums[n - 1]。

示例1：

输入：nums = [2,3,1,1,4]

输出：2

说明：到达最后一个索引的最小跳转次数为 2。从索引 0 到 1 跳转 1 步，然后跳转 3 步到最后一个索引。

示例2：

输入：nums = [2,3,0,1,4]

输出：2

限制：

1 <= nums.length <= 104

0<= nums[i] <= 1000

保证可以达到nums[n - 1]。

以下是我的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]

代码说明：

我从目标（最后一个索引）到数组的开头进行循环。每次我处于任何位置时，我都会将该位置的值更新为到达目标所需的最小跳跃次数。第二个 for 循环是遍历该位置的每一个可能的跳跃，看看哪一个会导致实现目标的最小步骤。 （所以每次我完成一个位置时，该位置的值就是朝着目标的最小跳跃）。

问题：

在我的算法中，每次我都会尝试找到最佳解决方案（在这种情况下，达到目标的最小跳跃次数）。那么这算不算贪心算法呢？如果不是，那么要成为这样的人到底缺少什么？这个问题的其他方法非常不同，所以我不确定。

我感谢任何帮助。

Answer 1

您的解决方案使用动态规划，将问题分解为子问题并使用之前计算的结果来解决更大的问题。

贪心算法通常不需要尝试所有可能的方法，而是有一套策略，在每一步直接选择最佳决策。