45. Jump Game II

DFS(TLE)

class Solution {
    private static class MinPathHolder{
        private int minJumpCount = Integer.MAX_VALUE;
    }

    public int jump(int[] nums) {
        int targetIndex = nums.length - 1;
        MinPathHolder minPathHolder = new MinPathHolder();
        dfs(nums, minPathHolder, 0,0, targetIndex);
        return minPathHolder.minJumpCount;
    }

    private void dfs(int[] nums, MinPathHolder minPathHolder,int jumpCount, int startIndex, int targetIndex) {
        if (startIndex >= targetIndex) {
            minPathHolder.minJumpCount = Math.min(minPathHolder.minJumpCount, jumpCount);
            return;
        }

        for (int i = 1; i <= nums[startIndex]; i++) {
            dfs(nums, minPathHolder, jumpCount + 1, startIndex + i, targetIndex);
        }
    }
}

DP

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

class Solution {
    public int jump(int[] nums) {
        int minJumpTimes = 0;
        int start = 0, end = 0; // 注意 start 与 end 初始值均为 0, 表示首次跳跃前，且 nums = [0] 时跳跃 0 次即可到达最后一个元素，所以 minJumpTimes 也要初始化为 0

        while (end < nums.length - 1) {
            int rightmost = end;

            for (int k = start; k <= end; k++) {
                rightmost = Math.max(rightmost, k + nums[k]);
            }

            start = end;
            end = rightmost;

            minJumpTimes++;
        }

        return minJumpTimes;
    }
}

Reference

45. Jump Game II