Spiderman and Jumping editorial

general
1

I can’t seem to find the correct approach for this question, and would be glad if someone explained the algorithm, or at least the logic to use.

here’s the link: CodeChef: Practical coding for everyone

1 Like
2

Let DP[i] be the minimum energy required to reach the ith building.

Then DP[i] can be found out by this relation :

DP[i] = min( DP[i],DP[i - 2^k] + abs(H[i] - H[i - 2^K]) ) where k goes from 0 to j such that 2^j is the largest power of 2 less than i.

Base Condition : DP[1] = 0

and also initialize each DP[i] to infinite at the start.

4 Likes
3

answer is DP[n]

4

So is dynamic programming a must for this?

5

because i havent learned it yet

6

this is really basic dp. Just think of this as a way of using previous results we have found to find current result. Do you know recursion ??

7

yes, i do know recursion, so code aside, can you just give me the steps, the logic in plain language, ur thought process

8

suppose we have to find the min energy required to reach building i. The buildings from which we can jump to i are i - 1, i - 2, i - 4… Suppose we already know the mid energy required to reach i-1,i-2,i-4… Then simply the min energy required to reach ith building from i - 2^kth building is |height[i]-height[i-2^k]| + min energy required to reach i - 2^kth building. We find the minimum for each k and that is the answer for ith building

1 Like