Minimum no. of jumps needed to reach at the end of array

Minimum no. of jumps needed to reach at the end of array

  June 18, 2017    

---

Idea:
Check with all the jumps that can be taken to reach at position i and choose the minimum jump

Here is solution by using dynamic programming

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static int check(int arr[],int n)
     {
         int jumps[]=new int[n];
         if(n==0 || arr[0] == 0)
         return -1;
         jumps[0]=0;
         for(int i=1;i<n;i++)
         {
             jumps[i]=Integer.MAX_VALUE;
             for(int j=0;j<i;j++)
             {
                 if(i<=arr[j]+j && jumps[j]!=Integer.MAX_VALUE)
                 jumps[i]=Math.min(jumps[j]+1,jumps[i]);
             }
         }
         return (jumps[n-1]!=Integer.MAX_VALUE)?jumps[n-1]:-1;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int arr[]=new int[n];
   for(int i=0;i<n;i++)
   arr[i]=ab.nextInt();
   System.out.println(check(arr,n));
}
}
}