[LeetCode] 45. Jump Game II

problem : https://leetcode.com/problems/jump-game-ii/description/

DP Solution:

DP[i] = the minimal steps needed to reach position i

Time Complexity = O(N * Max(Nums[i]))

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_int = 2 ** 31 - 1
        
        dp = [max_int] * len(nums)
        dp[0] = 0
        
        for i in range(len(nums)):
            # The furthest postion can be reached
            # from index i is nums[i+nums[i]].
            #
            # However, there is routine with less step 
            # to reach to nums[i+nums[i]].
            #
            # So including nums[i] in routine does not
            # decrease the total steps
            if i + nums[i] < len(nums) and dp[i] + 1 >= dp[i + nums[i]]:
                continue
                
            for j in range(1, nums[i]+1):
                if i + j >= len(nums) - 1:
                    dp[-1] = min(dp[-1], dp[i] + 1)
                else:
                    dp[i+j] = min(dp[i+j], dp[i]+1)
        
        return dp[-1]

Greedy Solution:

Time Complexity = O ( N )

class Solution:
    def jump(self, nums: List[int]) -> int:
        result = 0
        last_furthest = 0
        furthest = 0
        
        for i in range(0, len(nums) - 1):
            # Extend the furthest position can be reached
            if furthest >= i and nums[i] + i > furthest:
                furthest = nums[i] + i
            
            # If current position equals to the last furthest position
            # can be reached or it equals to the end of list, increase step counter. 
            # As it needs one more step to reach to the current furthest position.
            if i == last_furthest or furthest >= len(nums) - 1:
                last_furthest = furthest
                result += 1
            
            if furthest >= len(nums) - 1:
                break
        
        return result