leetcode：55. Jumping game [classic greed]

analysis

Maintain the current position , And the farthest position to be reached next time in the current maximum range maxPos
The current walking position is [cur, maxPos] But in the process of walking , Walk and watch the next maxPos, Then when cur Go to the previous maxPos when , next maxPos Come out, too
So this is walking at the foot , Looking at the greed ahead
The greedy strategy is ： I walk wherever I can , See the longest distance you can walk next time
The next longest distance I can walk is the largest in the current range nums[i] + i
Finally, take a look at cur Can you get there len(nums) - 1 that will do

ac code

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cur, maxPos = 0, 0

        #  The maximum range that can be taken in this step 
        while cur < maxPos + 1:
            #  The current position , To the farthest point you can walk 
            for i in range(cur, maxPos + 1):
                #  Update the next farthest location 
                maxPos = max(maxPos, nums[i] + i)
                #  If you come to the end step by step 
                if cur == len(nums) - 1:
                    return True
                # cur  and  i Corresponding 
                cur += 1
        
        return False

summary

Jumping game Follow The car refueling game is almost the same
Classic greed