All Tracks>Algorithms> Dynamic Programming> 2 Dimensional> Problem
Winter Jump
★★★★★

3.4

5 votes
Algorithms, 2D dynamic programming, Dynamic Programming
Problem

Problem

There is a city named Hackerland having N number of buildings .We are given the height array H of the buildings in the city. We are stuck at one end of the city and we need to go to the other end. We start from the first building and want to reach the last building.

We can jump to any of the next K buildings in front of us from our current building with a constraint such that we cannot make a jump of height difference larger than the jump before it except the first building where we can make a jump of any height difference. 

What are the minimum jumps required to reach the last building of the city ?

Input Format :

  • The first input line contains two integer N and K, denoting the number of buildings and number of buildings we can jump at most from current building.
  • The second line contains N space-separated integers denoting the elements of array H

Output Format:

Print the minimum jumps to reach the last builiding or in case we cannot reach print −1.

Constraints:

1≤N≤4∗103

0≤K≤4∗103

0≤H[i]≤N

 

Sample Input
6 2
3 1 5 1 4 3
Sample Output
3
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Here , the minimum steps required to reach the last building is 3. We can do jumps following the order  1->3->5->6.

Also note that if we jump from 1st building to 2nd building ,we cannot make a jump to 3rd building now but can jump to 4th building as height difference of 1 and 2 is abs(1-3)=2 which is less than height difference of 2 and 3 is abs(5-1)=4 whereas height difference of 2 and 4 is abs(1-1)=0 .
 

Contributers:
Editor Image

?