문제

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

구현 전 예상 풀이

dp, memoization방법으로 각 인덱스를 방문후 백 트래킹 할 때 거쳐온 인덱스의 최소 개수를 리턴하겠다.

구현 코드

class Solution {
    private int[] nums;
    private final int lastIdx = 10000;
    private final int[] dp = new int[lastIdx];

    public int jump(int[] nums) {
        this.nums = nums;
        dp[0] = 1;

        return recJump(nums.length - 1, 0) - 1;
    }

    private int recJump(int idx, int length) {
        if (nums[idx] < length) {
            return lastIdx;
        }

        if (dp[idx] != 0) {
            return dp[idx];
        }

        int minCnt = lastIdx;

        for (int i = 1; i <= idx; i++) {
            int cnt = recJump(idx - i, i);
            minCnt = Math.min(minCnt, cnt);
        }

        return dp[idx] = minCnt + 1;
    }
}

다른 사람 풀이

public int jump(int[] A) {
int step_count = 0;
int last_jump_max = 0;
int current_jump_max = 0;
for(int i=0; i<A.length-1; i++) {
    current_jump_max = Math.max(current_jump_max, i+A[i]);
    if( i == last_jump_max ) {
        step_count++;
        last_jump_max = current_jump_max;
    } 
}
return step_count;

45. Jump Game II
다른 사람 풀이 링크