Be the first user to complete this post

Add to List 
Dynamic programming – Minimum Jumps to reach to end
Objective: Given an array of nonnegative 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. The optimum result is when you reach the goal in the 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 the current index is ‘k’, then try out all the jumps from 1 to k.
 Each time you jump to the new index. Follow step 2 recursively.
 Base cases are –
 Check if your start index and end index are the same then no further jumps are required, return 0.
 If the value on the start index is 0, then we can pass through that index, and return Integer.Max
 Calculate the remaining Length in the array which is yet to be traveled. If the remaining length is less than the value at the present index then we do not need further recursion, we can reach the destination in one jump so return 1.
Code:
https://gist.github.com/thmain/ac42ae00dd46154555a484090e5fa0a3
Dynamic Programming Top Down
If we look closely at the diagram above we are solving many subproblems recursively. Here we will use Topdown approach of dynamic programming. We will use Hash Map to store the subproblem results and whenever we make a recursive call, first check if the subproblem is already solved, if yes then use it.
Code:
Output:
Minimum Jumps required: 9 Dynamic Programming  Time taken: 0 miliseconds
Also Read: