Cheapest Way Across the Pond

A frog crosses a pond over a row of \(n\) lily pads, numbered 0 to \(n - 1\). Landing on pad \(i\) costs \(c_i\). The frog starts on the near bank, just before pad 0, and has to reach the far bank, just after pad \(n - 1\). Every jump moves it forward by 1 or 2 positions, counting the two banks as positions:

• From the near bank it can land on pad 0 or pad 1.
• From pad \(i\) it can land on pad \(i + 1\) or pad \(i + 2\).
• From pad \(n - 2\) or pad \(n - 1\) it can reach the far bank.

The banks cost nothing. Implement min_crossing_cost(costs) returning the smallest total cost of the pads the frog lands on.

With no pads the frog is already across, so the answer is 0. With one pad it can jump straight over it, so the answer is 0 as well.

Examples

min_crossing_cost([10, 15, 20])
# 15  (bank -> pad 1 -> far bank)

min_crossing_cost([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])
# 6  (pads 0, 2, 4, 6, 7 and 9)

Constraints

• \(0 \le n \le 10^5\).
• \(0 \le c_i \le 10^9\). A total can pass \(2^{31}\), so it needs a 64-bit integer.
• A plain recursion that tries both jumps from every pad makes about \(1.6^n\) calls and will not finish even for \(n = 60\). In Python, a recursion one call deep per pad also runs past the default recursion limit of 1000 on the longest rows.

In C++

long long min_crossing_cost(const std::vector<long long>& costs);