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
- 1 ≤ n ≤ 10^4
- 1 ≤ k ≤ 100
- 0 ≤ h[i] ≤ 10^4
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
- The last jump into stone i came from one of the k stones before it.
- 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