Minimum number of jumps to reach end

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Example:

Input: arr[] = {1, 2, 5, 7, 6, 2, 6, 3, 2, 8, 9}
Output: 3 (1-> 2 -> 7 ->9)

First element is 1, so can only go to 2. Second element is 2, so can make at most 2 steps eg to 5 or 7.

Solution - we can do it with several methods.

              (1) recursion         (2) DP

here i'll only discuss the dynamic programming approach

(1) Time - O(n^2)  & Space - O(n)

       In this method, we will maintain an array from left to right such that the array contains information about  minimum number of jumps needed to reach ar[i] from ar[0]. So the nth element of the new array will have the information about minimum number of steps to reach the end.

#include<bits/stdc++.h>                                                                                                 using namespace std;

// Returns minimum number of jumps to reach nth step from the first

int minjumps(int ar[], int n){

    int jump[n+2];  // jump[n-1] will hold the result

    if (n == 0 || ar[0] == 0) //impossible situation

        return INT_MAX;

    int i,j;

    for(i=0;i<n;i++)

    jump[i]=INT_MAX;

    jump[0] = 0; //no of step to reach the first step

    // Find the minimum number of jumps to reach arr[i]

    // from arr[0], and assign this value to jumps[i]

    for (i = 0; i < n; i++){

        for (j = 1; j <= ar[i] && i+j<n; j++){

            jump[i+j]=min(jump[i+j],jump[i]+1);

        }

    }

    return jump[n-1];

}

int main()

{

    int ar[100000],n,i,j;

    scanf("%d",&n);

    for(i = 0; i < n; i++){

        scanf("%d",&ar[i]);

    }

    printf("Minimum number of jumps to reach end is %d ", minjumps(ar,n));

    return 0;

}

(2) Time - O(n) & Space - O(n) - 

basically i used the information that if we updated an index once then we don't need to update that for further numbers, because whatever we'll try we can't get less steps then that.

#include<bits/stdc++.h>                                                                                              using namespace std;

// Returns minimum number of jumps to reach nth step from first

int minjumps(int ar[], int n){

    int jump[n+2];  // jump[n-1] will hold the result

    if (n == 0 || ar[0] == 0) //impossible situation

        return INT_MAX;

       int i,j;

    jump[0] = 0; //no of step to reach the first step

    // from arr[0], and assign this value to jumps[i]

    int k=0; //this will avoid repeat for (i = 0; i < n; i++){ for (j = k+1; j <= i+ar[i] && j<n; j++) { jump[j]=jump[i]+1; } k=max(k,i+ar[i]); }

    return jump[n-1];

}

int main()

{

    int ar[100000],n,i,j;

    scanf("%d",&n);

    for(i = 0; i < n; i++){

        scanf("%d",&ar[i]);

    }

    printf("Minimum number of jumps to reach end is %d ", minjumps(ar,n));

    return 0;

}