Practice › Dynamic Programming
Frog Jump
Easy · Dynamic Programming · Asked at Amazon, Microsoft, TCS, Infosys
A frog stands on stone 1 and wants to reach stone n. From stone i it can jump to stone i + 1 or i + 2; a jump from i to j costs |h[i] − h[j]|. Print the minimum total cost.
Input
First line: n. Second line: n space-separated integers.
Output
The minimum cost.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ h[i] ≤ 10^4
dp[i] = min(dp[i−1] + |h[i]−h[i−1]|, dp[i−2] + |h[i]−h[i−2]|). Only the last two values are needed.
Example 1
Input
4 10 20 30 10
Output
20
Example 2
Input
3 10 50 10
Output
0
Hints
- To reach stone i, the last jump came from i − 1 or i − 2.
- dp[i] = min(dp[i−1] + |h[i] − h[i−1]|, dp[i−2] + |h[i] − h[i−2]|), with dp[0] = 0.
Approach
Define dp[i] as the minimum cost to stand on stone i. Every way to reach i ends with a jump from i − 1 or i − 2, so take the cheaper of the two options. Only the previous two values are needed, so two variables replace the array.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> h(n);
for (auto &x : h) cin >> x;
long long prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]
for (int i = 1; i < n; i++) {
long long cur = prev1 + llabs(h[i] - h[i - 1]);
if (i > 1) cur = min(cur, prev2 + llabs(h[i] - h[i - 2]));
prev2 = prev1;
prev1 = cur;
}
cout << prev1 << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
h = data[1 : 1 + data[0]]
prev2 = prev1 = 0
for i in range(1, len(h)):
cur = prev1 + abs(h[i] - h[i - 1])
if i > 1:
cur = min(cur, prev2 + abs(h[i] - h[i - 2]))
prev2, prev1 = prev1, cur
print(prev1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] h = new long[n];
for (int i = 0; i < n; i++) h[i] = sc.nextLong();
long prev2 = 0, prev1 = 0;
for (int i = 1; i < n; i++) {
long cur = prev1 + Math.abs(h[i] - h[i - 1]);
if (i > 1) cur = Math.min(cur, prev2 + Math.abs(h[i] - h[i - 2]));
prev2 = prev1;
prev1 = cur;
}
System.out.println(prev1);
}
}