**Objective**: Given an array of non negative integers, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps.

**Example:**

Given array A = {2,3,1,1,4} possible ways to reach the end (index list) i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index 4) ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4) Since second solution has only 2 jumps it is the optimum result.

**Approach**:

**Recursion-**

- Start from the index 0. Try out each option.
- If the value at current index is ‘k’, then try out all the jumps from 1 to k.
- Each time you jump to new index. Follow the step 2 recursively.
- Base cases are –
- Check if you start index and end index are same then no further jumps are required, return 0.
- If value on the start index is 0, then we can pass through that index, return Integer.Max
- Calculate the remaining Length in the array which is yet to be travelled. If remaining length is less than the value at the present index then we do not need further recursion, we can reach to the destination in one jump so return 1.

**Code:**

public class MinimumJumpsRecursion { | |

private int findJumps(int[] arr, int startIndex) { | |

//if reached to the end…we are done' | |

if(startIndex==arr.length–1){ | |

return 0; | |

} | |

int size = arr.length; | |

int remainingLength = size–startIndex; | |

if(remainingLength<=arr[startIndex]){ | |

//means no further recursion is required | |

return 1; | |

} | |

if(arr[startIndex]==0){ | |

System.out.println("Cannot move further"); | |

return Integer.MAX_VALUE; | |

} | |

int jumps = Integer.MAX_VALUE; | |

for (int i = 1; i <=arr[startIndex]; i++) { | |

int temp = findJumps(arr, startIndex+i); | |

if(temp!=Integer.MAX_VALUE){// check if path from jumps[j] is not blocked, means arr[startIndex]!=0 | |

jumps = Math.min(jumps, 1 + temp); | |

}else{ | |

//ignore…cannot pass through 0 | |

} | |

} | |

return jumps; | |

} | |

public static void main(String[] args) { | |

MinimumJumpsRecursion m = new MinimumJumpsRecursion(); | |

// int arr[] = {2, 5, 8, 9, 2, 6, 7, 6,1, 2, 5, 8, 9, 2, 6, 7, 6, 8, 9, 1, 1,6, 8, 9, 1,1,1}; | |

int arr[] = {1,3,4,8,9}; | |

long startTime = System.currentTimeMillis(); | |

System.out.println("Minimum Jumps required: " + m.findJumps(arr,0)); | |

long end = System.currentTimeMillis(); | |

System.out.println("Time taken: " + (end–startTime)/1000 + " seconds"); | |

} | |

} |

**Dynamic Programming- Top Down**

If we look closely the diagram above we are solving many sub problems recursively. Here we will use Top-down approach of dynamic programming. We will use Hash Map to store the sub problems results and whenever we make a recursive call, first check if the sub problem is already solved, if yes then use it.

**Code**:

import java.util.HashMap; | |

public class MinimumJumpsDP { | |

HashMap<Integer,Integer> map = new HashMap<Integer, Integer>(); | |

private int findJumps(int[] arr, int startIndex) { | |

//if reached to the end…we are done | |

if(startIndex==arr.length–1){ | |

return 0; | |

} | |

if(map.containsKey(startIndex)){ | |

return map.get(startIndex); | |

} | |

int size = arr.length; | |

int remainingLength = size–startIndex; | |

if(remainingLength<=arr[startIndex]){ | |

//means no further recursion is required | |

return 1; | |

} | |

if(arr[startIndex]==0){ | |

// System.out.println("Cannot move further"); | |

return Integer.MAX_VALUE; | |

} | |

int jumps = Integer.MAX_VALUE; | |

for (int i = 1; i <=arr[startIndex]; i++) { | |

int temp = findJumps(arr, startIndex+i); | |

if(temp!=Integer.MAX_VALUE){// check if path from jumps[j] is not blocked, means arr[startIndex]!=0 | |

jumps = Math.min(jumps, 1 + findJumps(arr, startIndex+i)); | |

}else{ | |

//ignore…cannot pass through 0 | |

} | |

} | |

map.put(startIndex,jumps); | |

return jumps; | |

} | |

public static void main(String[] args) { | |

MinimumJumpsDP m = new MinimumJumpsDP(); | |

long startTime = System.currentTimeMillis(); | |

int arr[] = {1, 3, 5, 3, 3,1,1,1,1,1,1,1,1,4}; | |

System.out.println("Minimum Jumps required: " + m.findJumps(arr,0)); | |

long end = System.currentTimeMillis(); | |

System.out.println("Dynamic Programming – Time taken: " + (end–startTime)+ " miliseconds"); | |

} | |

} |

**Output**:

Minimum Jumps required: 9 Dynamic Programming - Time taken: 0 miliseconds