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