Frog 1

Frog 1

Atcoder easy

You are given an array \(h\) with \(N\) elements. You start at the first element and must reach the last element using these moves:

• Move from index \(i\) to \(i + 1\) with a cost of \(|h_i - h_{i + 1}|\).
• Move from index \(i\) to \(i + 2\) with a cost of \(|h_i - h_{i + 2}|\).

Find the minimum total cost required to move from the first element to the last.

Note

In this task we’ll assume that everything is 0-indexed. That is, all arrays indexes will start with 0.

Solution

We will solve this problem using dynamic programming.

First, we’ll define the state \(f(i)\) to be the minimum cost to reach index i starting from index 0.

Next we’ll define the transition. There are two ways to reach stone \(i\): from \(i - 1\) and from \(i - 2\).

If we reach index \(i\) from \(i-1\), then \(f(i)\) is the minimum cost to reach \(i-1\) from \(0\) plus the cost of moving from \(i-1\) to \(i\).

\(f(i) = f(i - 1) + |h_{i - 1} - h_i|\)

If we reach index \(i\) from \(i-2\), then \(f(i)\) is the minimum cost to reach \(i-2\) from \(0\) plus the cost of moving from \(i-2\) to \(i\).

\(f(i) = f(i - 2) + |h_{i - 2} - h_i|\)

Since we don’t know which option is optimal we’ll take the minimum of both costs as our transition.

\(f(i) = min(f(i - 1) + |h_{i - 1} - h_i| , f(i - 2) + |h_{i - 2} - h_i|)\)

Our base case will be:

\(f(0) = 0\)

\(f(1) = |h_0 - h_1|\)

The space complexity of the algorithm is determined by the number of states, which is \(O(N)\).

The time complexity is the number of states \(N\) multiplied by the complexity of each transition \(O(1)\), so the overall time complexity is \(O(N)\).

#include <iostream>
using namespace std;

int a[200000];
// the array dp is used for memoization
int dp[200000];


int f(int i) {
    // base cases
    if (i == 0) {
        return 0;
    }

    if (i == 1) {
        return abs(a[1] - a[0]);
    }

    // if the solution has been already calculated
    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = min(
        f(i - 1) + abs(a[i] - a[i - 1]),
        f(i - 2) + abs(a[i] - a[i - 2])
    );

    return dp[i];
}


int main() {
  // assign -1 to all elements to indicate no solution has been calculated
    for (int i = 0; i < 200000; i++) {
        dp[i] = -1;
    }

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << f(n - 1) << "\n";
}