Intuition 🤔

이번이야말로 dynamic programming을 사용하면 될 것 같다.
nums와 같은 사이즈의 배열 (distanceArray)을 initialize한다. 각 칸에는 최종 위치까지 도달하는데 필요한 최소거리를 저장한다.
그리고 각 칸을 iterate할때마다 현재 위치에서 도달 가능한 칸들에 대하여 여태까지 계산했던 distanceArray의 값들을 비교해 최소 + 1을 저장한다.

초기 답안

class Solution {
    public int jump(int[] nums) {
        int length = nums.length; 
        int lastIndex = length - 1;

        if (length == 1) {
            return 0; 
        }

        int[] leastSteps = new int[length]; 
        int currentIndex = lastIndex - 1; 

        while (currentIndex >= 0) {
            int currentReachableDistance = nums[currentIndex]; 
            if (currentReachableDistance == 0) {
                leastSteps[currentIndex] = 1001;
            } else {
                int minimumDistance = Integer.MAX_VALUE;
                for (int i = 1; i <= currentReachableDistance; i++) {
                    int targetIndex = currentIndex + i;
                    if (targetIndex > lastIndex) {
                        break; 
                    } else { 
                        minimumDistance = Math.min(1 +leastSteps[targetIndex], minimumDistance); 
                    }
                }

                leastSteps[currentIndex] = minimumDistance; 
            }

            currentIndex -= 1; 
        }

        return leastSteps[0]; 
    }
}

답안

Greedy algorithm 을 사용하는 것이다. 제일 멀리 갈 수 있는 position을 정하고 이전에 정해진 position에 다다를때 jump count를 하나 올리고 다음 end position으로 업데이트한다.

class Solution {
    public int jump(int[] nums) {
        int jumpCount = 0; 
        int endPosition = 0; 
        int farthest = 0; 

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(i + nums[i], farthest); 

            if (i == endPosition) {
                endPosition = farthest;
                jumpCount++;
            }
        }

        return jumpCount; 
    }
}

i < nums.length - 1인 이유는 만약 endPosition이 nums.length - 1이라면 jumpCount 가 하나 더 늘어나기 때문이다.