Medium - Jump Game II

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

Jump Game II - LeetCode

문제 설명

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].

Constraints:

• 1 <= nums.length <= 10 ** 4
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

예시

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

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

풀이

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        table = [10000, ] * n
        table[0] = 0

        for i in range(n):
            for j in range(1, nums[i] + 1):
                if i + j >= n:
                    break

                table[i+j] = min(table[i+j], table[i]+1)

        return table[-1]

 

 

문제에서 설명하는 방법을 그대로 적용한 풀이.

 

테이블의 값은 각 인덱스까지 도달하는 최소값을 나타낸다.

1. index 0은 시작점이니 0으로 설정하고

2. nums[0 + x] (1 <= x <= nums[0]) 를 nums[0] + 1과 비교하며 더 작은 값을 nums[0 + x]에 대입한다.

3. 1 + y, 2 + z 등 다른 값들이 0 + x와 같을 수 있으므로 가능한 모든 방법을 비교할 수 있게 된다.

4. 모든 루프를 돌면 table[-1]은 마지막 인덱스에 도달하는 최소값이 된다.

 

시간복잡도가 n ** 2, 공간복잡도가 n이라서, 더 나은 다른 방법을 생각해보고 싶은데, 모르겠다.

분명히 n log n 짜리 DP 풀이가 있을 것 같은 문제인데.