[코딩/LeetCode150-(10)] 45. Jump Game II

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python3을 사용합니다.

 

 

 

난이도: Medium

키워드: Array, DP

 

문제

 

문제 원문: https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150 

 

정수형 배열 nums가 주어졌다고 하자. 당신은 처음에 배열의 첫번째 index에 위치한다. 그리고 배열의 각 원소는 해당 위치에서부터 당신이 최대로 점프할 수 있는 길이를 나타낸다. 이 때, 마지막 index 에 도달하는데 필요한 jump 수의 최솟값을 반환해라.

 

* 항상 nums[n-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.

 

풀이

Jump Game (55) 문제와 유사한 문제이다. 다만, 이 때 필요한 최솟값을 묻는 문제이므로, DP 값을 업데이트하는 방식만 수정하도록 코드를 업데이트해주었다.

 

class Solution:
    def jump(self, nums: List[int]) -> int:

        N = len(nums)

        # Initialize
        dp = [float("inf")] * N
        dp[-1] = 0

        for i in range(len(nums)-2,-1,-1):
            for j in range(i+1, min(i+nums[i]+1, N)):
                dp[i] = min(dp[i], 1 + dp[j])
        
        return dp[0]