Getting everything ready for you…

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

0s

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

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

  1. To reach stone i, the last jump came from i − 1 or i − 2.
  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);
    }
}

Solve Frog Jump online · All practice problems