[java] jump game 2

[참고 문제] : https://leetcode.com/problems/jump-game-ii/

Jump Game II - LeetCode

---

문제 풀이

생각의 흐름 - DP

Jump 하여 다음에 갈 위치와, 현재의 Score를 계산하는 방식이 필요할 것이라고 생각했다.

고로, DP로 풀이가 가능할 것이라고 판단

 

생각의 흐름 - 메모이제이션

무엇을 저장해야 할까가 그 다음 스텝이였다.

위에서 Score를 떠올렸으므로 nums와 같은 길이의 배열(arr)이 필요하고, 각 Index에 대해 최소한의 스텝으로 jump하는 Count를 비교/저장해야한다고 판단.

 

생각의 흐름 - 초깃값

초깃값은 문제에서 제시가 되었듯, arr의 0번째 Index는 0으로 초기화해야 한다고 판단.

결과적으로, nums가 1개인 경우도 해소되었다.

 

생각의 흐름 - 그냥 해보기

DP를 풀 때, 식이 생각이 안나면 0번째부터 쭉 써서 규칙을 찾는다.

이번에도 마찬가지로 규칙을 찾아서 아래와 같이 풀이하였다.

public int jump(int[] nums) {
    int len = nums.length;
    int[] arr = new int[len];
    Arrays.fill(arr, Integer.MAX_VALUE);
    arr[0] = 0;
    for(int i = 0; i < len; i++) {
        int jump1 = nums[i];
        int k = Math.min(i + jump1, len-1);
        for(int j = i+1; j <= k; j++) {
            arr[j] = Math.min(arr[j], arr[i] + 1);
        }
    }
    return arr[len-1];
}