Problem Statement

Given an array of integers where each element represents the maximum length of a jump that can be made forward from that element, find the minimum number of jumps you must make in order to get from the start to the end of the array.

For example, given the array {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}, the minimum number of jumps to reach the end is 3 (jump from 1st element to 2nd element with value 3, then to the 5th element with value 9, and finally to the last element).

Recursive Approach

The recursive solution involves exploring all possible jumps for each element and choosing the path that results in the minimum number of jumps. Here’s the Java code for the recursive approach:

class Solution {
    static int minJumps(int[] arr) {
        int n = arr.length;
        int result = minJumpsHelper(arr, 0);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    static int minJumpsHelper(int[] arr, int n) {
        if (n == arr.length - 1) {
            return 0;
        }

        if (arr[n] == 0) {
            return Integer.MAX_VALUE;
        }

        int minJumps = Integer.MAX_VALUE;
        for (int i = 1; i <= arr[n]; i++) {
            if (n + i < arr.length) {
                int jumps = minJumpsHelper(arr, n + i);
                if (jumps != Integer.MAX_VALUE) {
                    minJumps = Math.min(minJumps, jumps + 1);
                }
            }
        }

        return minJumps == Integer.MAX_VALUE ? Integer.MAX_VALUE : minJumps;
    }
}

Time Complexity: The time complexity of the recursive approach is exponential, O(2^n), because each element can potentially make a jump to every other element coming after it.

Space Complexity: The space complexity is O(n) due to the recursion stack.

Dynamic Programming Approach

The dynamic programming approach optimizes the recursive approach by storing the results of subproblems to avoid redundant computations. Here’s the Java code for the dynamic programming approach:

class Solution {
    static int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }
        if (arr[0] == 0) {
            return -1;
        }

        int[] jumps = new int[n];
        jumps[0] = 0;

        for (int i = 1; i < n; i++) {
            jumps[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (i <= j + arr[j] && jumps[j] != Integer.MAX_VALUE) {
                    jumps[i] = Math.min(jumps[i], jumps[j] + 1);
                    break;
                }
            }
        }

        return jumps[n - 1] == Integer.MAX_VALUE ? -1 : jumps[n - 1];
    }
}

Time Complexity: The time complexity of the dynamic programming approach is O(n^2) because we are using two nested loops.

Space Complexity: The space complexity is O(n) for the jumps array.

In conclusion, while the recursive approach provides a straightforward solution to the problem, the dynamic programming approach significantly improves the time complexity by avoiding redundant computations. For larger inputs, the dynamic programming approach is more efficient and practical.