Criteria for being considered as a greedy algorithm in specific context

Question

I have some trouble trying to understand whether an algorithm is greedy or not. From the definition, greedy algorithm is algorithm that make the best choice locally in order to make the global solution. However, the definition is quite broad and I am not sure how to know in specific case. There is 1 previous post talking about this but the problem is different so I want to ask again.

So specifically, here is the problem and the algorithm where I am not sure it is a greedy or not. This is leetcode 45:

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

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

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]

Output: 2

Constraints:

1 <= nums.length <= 104

0 <= nums[i] <= 1000

It's guaranteed that you can reach nums[n - 1].

Following is my solution in 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]

Code Explanation:

I do a loop from the goal (the last index) to the beginning of array. Every time I am at any position, I update the value of that position to the minimum number of jump required to reach the goal. The second for loop is to run through every possible jump of that position to see which would result in the minimum step toward goal. (So every time I am done with a position, that position's value is the minimum jump toward goal).

Question:

In my algorithm, for each time, I do try to find the best solution (in this case, minimum jumps to reach goal). So is this considered greedy algorithm? If not, what exactly does it lack to become one? Other approaches of this problem is quite different so I am not sure.

I appreciate any help.

Answer 1

Your solution uses dynamic programming by splitting the problem into subproblems and using previously computed results to solve larger problems.

Greedy algorithms usually do not need to try all possible ways, but have a set strategy for directly choosing the best decision at each step.