Popular Posts

Monday, February 13, 2012

Minimum number of jumps to reach last element


Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps


public class MinNumberOfJumps {
private static int MAX = 23234;

public static void main(String[] args) {
int[] jumps = { 2, 3, 1, 1, 4 };
int minJumps = getMinJumps(jumps, jumps.length);

if (minJumps < MAX)
System.out
.println("Minimum number of jumps needed to reach the end of the array is : "
+ minJumps);
else
System.out.println("Cannot reach the end position of the array");
}

private static int getMinJumps(int[] jumps, int size) {
//Boundry conditions
if (jumps == null || size == 0 || jumps[0] == 0)
return MAX;

int[] dp = new int[size];
//Initialization of dp[i]
for (int i = 0; i < size; i++)
dp[i] = MAX;

dp[0] = 0;//no need to jump at first element

for (int i = 1; i < size; i++) {
for (int j = 0; j <= i; j++) {
if (jumps[j] >= (i - j)) {//check if jump is possible from j to is
if (dp[j] + 1 < dp[i]) //check if better solution available
dp[i] = dp[j] + 1;
}
}
}
return dp[size - 1];
}

}

Refer  : http://avidullu.wordpress.com/2011/01/12/dp-after-a-long-time/
http://tech-queries.blogspot.in/2011/08/find-optimal-number-of-jumps-to-reach.html

No comments:

Post a Comment