Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Frog Jump with K Distances

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Adobe

Like "Frog Jump", but from stone i the frog can jump to any of the stones i + 1, i + 2, …, i + k. A jump from i to j costs |h[i] − h[j]|. Print the minimum total cost to reach stone n.

Input

First line: n k. Second line: the n heights.

Output

The minimum cost.

Constraints

dp[i] = min over j in [i−k, i−1] of dp[j] + |h[i] − h[j]|.

Example 1

Input

5 3
10 30 40 50 20

Output

30

Example 2

Input

3 1
10 20 10

Output

20

Hints

  1. The last jump into stone i came from one of the k stones before it.
  2. dp[i] = min over j from max(0, i−k) to i−1 of dp[j] + |h[i] − h[j]|.

Approach

Generalise Frog Jump: for each stone i, try every possible previous stone within distance k and keep the cheapest total. With n ≤ 10^4 and k ≤ 100 this is at most 10^6 transitions.

Complexity: O(n · k) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> h(n), dp(n, LLONG_MAX);
    for (auto &x : h) cin >> x;
    dp[0] = 0;
    for (int i = 1; i < n; i++)
        for (int j = max(0, i - k); j < i; j++) dp[i] = min(dp[i], dp[j] + llabs(h[i] - h[j]));
    cout << dp[n - 1] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
h = data[2 : 2 + n]
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i))
print(dp[-1])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] h = new long[n], dp = new long[n];
        for (int i = 0; i < n; i++) h[i] = sc.nextLong();
        for (int i = 1; i < n; i++) {
            dp[i] = Long.MAX_VALUE;
            for (int j = Math.max(0, i - k); j < i; j++) dp[i] = Math.min(dp[i], dp[j] + Math.abs(h[i] - h[j]));
        }
        System.out.println(dp[n - 1]);
    }
}

Solve Frog Jump with K Distances online · All practice problems