Dynamic Programming 06

Given an array of N integers arr[] where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.

Problem link :- click here

Code

import java.util.Scanner;

// MINIMUM NUMBER OLF JUMPS

public class DynamicProgramming_06
{
	
	// Recursion
	static int minJumps(int arr[], int cur,  int last)
	{
		if(cur == last)
			return 0;
		
		if(arr[cur] == 0)
			return -1;
		
		if(cur + arr[cur] >= arr.length - 1)
			return 1;
		
		int minJumps = Integer.MAX_VALUE;
		for(int i=cur+arr[cur]; i<=last && i<=cur+arr[cur]; i++)
		{
			int jumps = minJumps(arr, i, last);
			if(jumps + 1 < minJumps)
				minJumps = jumps + 1;
		}
		
		return minJumps;
	}
	
	// Dynamic Programming
	static int minJumps2(int arr[])
	{
		int n = arr.length;
		int jumps[] = new int[n];
		
		jumps[n-1] = 0;
		
		if(arr[n-2] > 0)
			jumps[n-2] = 1;
		else
			jumps[n-2] = Integer.MAX_VALUE;
		
		for(int i=n-3; i>=0; i--)
		{
			// if we can reach the last element with current number of steps 
			// then number of jumps required is 1 (directly to last element)
			if(arr[i] >= (n-1)-i)
				jumps[i] = 1;
			else
			{
				//here we have compare all the reachable elements from cur index
				//and jump to element which has minimum number of jumps
				int min = Integer.MAX_VALUE;
				for(int j=i+1; j<n && j<=i+arr[i]; j++)
					if(jumps[j] + 1 < min)
						min = jumps[j] + 1;
				jumps[i] = min;
			}
		}
		
		return jumps[0];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		int arr[] = new int[n];
		
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		int ans = minJumps(arr, 0,  n-1);
		System.out.println(ans);
		
		int ans1 = minJumps2(arr);
		System.out.println(ans1);
		
		s.close();
	}

}