45. Jump Game II

,

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;

        // 定义 dp[i] 为跳跃至索引 i 最小的跳跃次数
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);                
            }
        }

        return dp[n - 1];
    }
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int jump(int[] nums) {
        int times = 0;

        int startIndex = 0, endIndex = 0; // [startIndex, endIndex]
        while (endIndex < nums.length - 1) {
            int nextStartIndex = endIndex + 1;
            int nextEndIndex = nextStartIndex;
            for (int i = startIndex; i <= endIndex; i++) {
                nextEndIndex = Math.max(nextEndIndex, i + nums[i]);
            }

            startIndex = nextStartIndex;
            endIndex = nextEndIndex;
            times++;
        }

        return times;
    }
}

References

45. Jump Game II