import java.util.*;
 
/**
 * Given an jumpsay 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 jumpsay (starting from the first element). 
 * If an element is 0, then cannot move through that element.
 *
 * Example:
 * 	Input: jumps[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
 * 	Output: 3 (1-> 3 -> 8 ->9)
 *
 * 	First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps eg to 5 or 8 or 9.
 *
 * 	If an element is 0, then cannot make any jumps
 */
class Ideone {
	private static final int MAX = 10000;
	public static void main(String[] args){
		int[] jumps = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
 
		if(jumps[0] == 0){
			System.out.println("No jumps are allowed from the first step.");
			return;
		}
 
		//To hold min number of jumps needed to reach that step from starting step
		int[] dp = new int[jumps.length];
 
		for(int i=1; i<jumps.length; i++){
			dp[i] = MAX; //initialise min steps to MAX value
 
			//Calculate min jumps need to reach ith Step
			for(int j=0; j<i; j++){
				if(j + jumps[j] >= i && dp[j] != MAX){
					dp[i] = dp[j]+1;
					break;
				}	
			}
		}
 
		System.out.println("Minimum number of jumps to reach other end => "+ dp[jumps.length-1]);
	}	
}