Given an array 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 array (starting from the first element).
If an element is 0, then cannot move through that element.
Example:
Input: arr[] = {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.
http://www.programcreek.com/2014/03/leetcode-jump-game-java/
http://www.programcreek.com/2014/06/leetcode-jump-game-ii-java/
Method 1:Greedy Approach(Doesn't Gives Optimal Solution)
We Know that from ith location we can jump only maximum a[i] , so greedly we will keep goin & icrementing the jump untill we won't reach end of the array.
so in loop i=0 to size of array we will iterate through a[i] & w3ill check if a[i+j]+j ie greater then max or not if its true then we will update the max & repat the same logic. this we will reach to end of the array but doesn't gurantee that it will be optimal. e.g. fro above case it will return 3 jumps but for this case 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1 which requires minimum number of jumps is 3 but this algo will produce jump 4.
Code:
#include <stdio.h>
int main()
{
int arr[]={1, 3, 5 ,8 ,9 ,2 ,6, 7, 6, 8, 9};
int size=sizeof(arr)/sizeof(int);
int i=0,jump=0,step,max,j;
while( i< size)
{ jump++; max=0; step=0;
/*computes max distance it can cover in this jump*/
for(j=1;j<=arr[i];j++)
{ if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}
printf("%d ",jump);
getchar();
return 0;
}
Time Complexity O(N^2)
Space Compelxity O(1)
Method 2:Recursion
A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.
minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start
#include <stdio.h>
#include <limits.h>
int minJumps(int arr[], int l, int h)
{
// Base case: when source and destination are same
if (h == l)
return 0;
// When nothing is reachable from the given source
if (arr[l] == 0)
return INT_MAX;
// Traverse through all the points reachable from arr[l]. Recursively
// get the minimum number of jumps needed to reach arr[h] from these
// reachable points.
int min = INT_MAX;
for (int i = l+1; i <= h && i <= l + arr[l]; i++)
{
int jumps = minJumps(arr, i, h);
if(jumps != INT_MAX && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
int main()
{
int arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8,9,1,1,1};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of jumps to reach end is %d ", minJumps(arr, 0, n-1));
getchar();
return 0;
}
Method 3:Dynamic Programing-Top Down
In this method, we build a jumps[] array from left to right such that jumps[i] indicates the minimum number of jumps needed to reach arr[i] from arr[0]. Finally, we return jumps[n-1].
#include <stdio.h>
#include <limits.h>
int minJumps(int arr[], int n)
{
int *jumps = new int[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
jumps[0] = 0;
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++)
{
jumps[i] = INT_MAX;
for (j = 0; j < i; j++)
{
if (i <= j + arr[j] && jumps[j] != INT_MAX)
{
jumps[i] = jumps[j] + 1;
break;
}
}
}
return jumps[n-1];
}
int main()
{
int arr[]= {1, 3, 5, 8, 9, 2, 6, 7, 6, 8,9,1,1,1};
int size=sizeof(arr)/sizeof(int);
printf("Minimum number of jumps to reach end is %d ", minJumps(arr,size));
getchar();
return 0;
}
Time Complexity:O(n2)
Method 4:Dynamic Programming-Botttom Up
