Minimum Number of steps to reach the end in an array

Problem :

We have an array A[ ] where each element A[ i ] specifies the maximum number of jumps we can move forward from that position, we need to  find the
minimum number of jumps to reach the end of the array from the begining .

Solution :
We can solve this problem in multiple approaches. Here i am going to provide solution in greedy and dynamic programming model.

In greedy approach we find the maximum value to maximize the jump. In dynamic programming approach we compute the minimum number of hops required to reach each element and use these values for computing the result.

 Using  Dynamic programming ,this can be solved b y finding the minimum number of steps to reach the n-1 position and then checking for the minimum of {jumps[i],jumps[j]+1} where
j ranges from 0-i and also satisfies the formula i-j <= A[j].

Assume we have a array sequence {1, 2, 1,1,4,6,2,0,8}

Assume we are processing A[2]=1 and we need to find the minimum no of jumps to reach A[4]=4

Now the formula will not be satisfies as to reach A[4] we need to have a value of A[j] which can be used to fill the gap from i to j that (i-j).  So it has to satisfy (i-j)<=A[j].

Jumps[i] = Min { Jumps[i], Jumps[j] + 1}

C++ Code:

#include "stdafx.h"
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
int _tmain(int argc, _TCHAR* argv[])
{
    int a[]={1,2,3,1,1,5,0,8};

    int n;
    int *JP;
    //std::cout<<"Enter sum value :\n";
    //std::cin>>n;
    JP= new int[8];

    JP[0]=0; //base, to jump to position 0.
    for(int i = 1;i<8;i++)
    {
        //Set maximum for a position of i.
        JP[i] = INT_MAX;
        //For each postion, check the no of ways to reach using the previous postion values.
        //And select the lowest in each run.
        int count = 0;
        for(int j=0;j<i ;j++)
        {
          
            if(a[j]>=(i-j))
            {
                count++;
                if(JP[i] >JP[j]+1)
                {
                    JP[i] = JP[j]+1;
                  
                }
            }
          
        }
        std::cout<<" Number of ways to reach position "<< a[i] << " is :"<<count<<" Min hops :"<<JP[i]<<std::endl;
    }
    std::cout<<" Min Number of hops to reach the end of the array is :"<<JP[7]<<std::endl;
}

Java Code :

 public class FindMinimumHops {
   
    public static void main(String args[])
    {
        int [] array = {2,3,1,1,4};
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingGreedy(array));       
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingDP(array));
    }

    private static int findMinHopsUsingGreedy(int[] array) {
        int maxHops = 0;
        int currentIndex = 0;
        int max = 0;
        int location = 0;
        while (currentIndex < array.length) {
            maxHops++;
            max = 0;
            for (int ctr = currentIndex + 1; ctr <= currentIndex
                    + array[currentIndex]; ctr++) {
                if (max < array[ctr]) {
                    max = array[ctr];
                    location = ctr;
                }
            }
            currentIndex += location;
        }
        return maxHops;
    }

    private static int findMinHopsUsingDP(int[] array) {
        int []dp = new int[array.length];
        dp[0] = 0;
        for(int i = 1; i < array.length; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            for(int j= 0; j < i ; j++ )
                if( ( i-j ) <= array[j] )
                    dp[i] = Math.min(dp[i], dp[j]+1);
        }
       
        return dp[array.length - 1];
    }

}

Thanks to Gopal for sharing the Java Code.