FastPrep
Problem · Array

Minimum Jump Cost

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

There are n points on the x-axis at coordinates 1, 2, 3, ..., n. The i-th point has an associated cost cost[i].

Starting from coordinate x = 0, you can make jumps of length at most k. Whenever you stop at a point, you incur the cost of that point.

Find the minimum total cost required to reach point n.

Function

getMinimumCost(cost: int[], k: int) → long

Examples

Example 1

cost = [4,3,9,3,1]k = 2return = 7

The optimal jump pattern is 0 -> 2 -> 4 -> 5. The cost of stopping at points 2, 4, and 5 is 3 + 3 + 1 = 7, which is the minimum possible.

Example 2

cost = [1,2,3,4]k = 2return = 6

The optimal path is 0 -> 2 -> 4, with total cost 2 + 4 = 6.

Constraints

  • 1 <= n <= 3 * 10^5
  • 1 <= k <= n
  • 1 <= cost[i] <= 10^9

More Microsoft problems

drafts saved locally
public long getMinimumCost(int[] cost, int k) {
  // write your code here
}
cost[4,3,9,3,1]
k2
expected7
checking account