45. Jump Game 2

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

DP list에 각 nums 인덱스에 도달할 수 있는 최소 회수를 저장하도록 함

class Solution:
    def jump(self, nums: List[int]) -> int:
        INF = 1e9
        length = len(nums)
        
        dp = [INF for i in range(length)]
        dp[0] = 0
        
        for i in range(length-1):
            now = nums[i]
            for dx in range(now):
                dx+=1
                if i + dx < length:
                    dp[i+dx] = min(dp[i+dx], dp[i] +1)
        
        return dp[-1]

문제는 실행시간이 끔찍하게 느리다는 점.

문제점 1. if로 length 를 넘는지를 계속 체크한다 -> 그냥 maximum list 사이즈를 확인한 후 dp list를 선언하면 length면 되는걸 length*평균(nums) 만큼 if를 더 태워버린 꼴

문제점 2. 애초에 이런 방식으로는 O(length * 평균(nums))임. 다른 방법을 찾아보니 시간복잡도 O(length)만으로 되는 코드를 발견

class Solution:
    def jump(self, nums: List[int]) -> int:
        last_index = len(nums) - 1
        max_reachable=[start_pos+nums[start_pos] for start_pos in range(last_index)]
        jump_range = (0, 0)
        n_jumps = 0
        while jump_range[1] < last_index:
            n_jumps += 1
            jump_range = (jump_range[1], 
            				max(max_reachable[jump_range[0]:jump_range[1]+1]))
        return n_jumps

각 time step 마다 도달할 수 있는 최대거리를 dp list에 저장하는 방식