Find optimal number of jumps to reach last element

Question: Given an array, 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)

1. 0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
2. 0,1,4 (jump 1 to index 1, and then jump 3 to index 4)

Since second solution has only 2 jumps it is the optimum result.

Answer: This problem is a classic example of Dynamic Programming. Though we can solve this by brute-force but complexity in that case will be horrendous. If you remember LCS problem or my max sum of non consecutive elements in the array then we can solve this by using same process.

As soon as we traverse the array, we should find the minimum number of jumps for reaching that position (index) and update our result array. Once we reach at the end, we have the optimum solution at last index in result array.

How to find optimum number of jump for every position (index)?

For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.

So consider this array :  2,3,1,1,4
element possible indices
 2 -       0, 1, 2
3 -        1, 2, ,3 4
1           2,3
1            3,4
4          end 

For (N+1)^th element, initialize result[N+1] as infinite. Then we should go through a loop from 0…N, and at every index (i), we should see if we are able to jump to (N+1) from there (i) or not. If possible then see if total number of jump (result[i] + 1) is less than result[N+1], then update result[N+1] else just continue to next index.

      result[i] = INT_MAX if a[i] == 0

      result[i] = 1 + min(result[j]  where j is from i + 1 to i + a[i]

Code: I skipped algorithm but commented code properly...code being in java.

//Define MAX 1 less so that adding 1 doesn't make it 0
public static int minNumberOfHops(int array[])
{
 int MAX = Integer.MAX_VALUE;
 int n = array.length;
 int  result[] = new  int[n];
 int i, j;
  //Boundry conditions
 if (n==0 || array[0] == 0)
  return MAX;
 result[0] = 0;  //no need to jump at first element
 for (i = 1; i < n; i++)
 {
  result[i] = MAX; //Initialization of result[i]
  for (j = 0; j < i; j++)
  {
   //check if jump is possible from j to ith node
   if (array[j] >= (i-j))      {
    //check if better solution available
      if ((result[j] + 1) < result[i]) 
        result[i] = result[j] + 1;  //updating result[i]
    }
  }
 }

 //return result[n-1]
 int answer = result[n-1];


 return answer;
}

Dry running the algo
Array : [2, 3, 1, 1, 4]
n = 5
result : [0 0 0 0 0 ]
MAX - 2147483647 (in java)

Now lets run through the loops
i = 1, j =0
result - [0, 2147483647, 0, 0, 0]  (setting MAX at the i th position)
Now suppose X =  (arr[j] > i-j) , Y = (result[j]+1 < result [i])
X tests if jump is possible from index j to index i. 
Y tests if better condition exists, such that result[i] > result[j]+1....i.e. if hop is possible from j to i...then minimize result[i]....
if X AND Y then set result[i] = result[j] + 1
result = [0, 1, 0, 0, 0]

i = 2, j = 0
result - [0, 1, 2147483647, 0, 0]
Condition check
result = [0, 1, 1, 0, 0]
i =2 , j=1
No change in result

i = 3, j =0
result = [0, 1, 1, 2147483647, 0]
X = false
i=3, j = 1
X = true, Y = true
result = [0, 1, 1, 2, 0]
i=3, j=2
X=true, Y=false

i=4,j=0
result - [0, 1, 1, 2, 2147483647]
X=false
i=4, j=1
X=true, Y=true
result - [0, 1, 1, 2, 2]
i=4, j=2
X=true, Y=false
i=4, j=3
X=true, Y=false

answer=2
Also note that the result matrix gives us the indices as well - from 0 ->1, 1 ->3 ....(take the note of indices where the value changes)...So this happens only 2 times.

Complexity
Above code will return optimum number of jumps only. If we want to have the jump indexes as well, we can very easily modify the code as per requirement. Efficiency: Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1). So time efficiency O(n) = O(n*(n-1)/2) = O(n^2) We also need O(n) space for result array.