算法

(递推型DP) $O(n)$

状态定义：

dp[i]: 青蛙从第 i 块石头跳到第 $n$ 块石头所需的最小成本

状态转移：

$$ dp[i] = \begin{cases} \min(dp[i + 1] + |h[i] - h[i + 1]|, dp[i + 2] + |h[i] - h[i + 2]|), & i + 2 \leqslant n \\\ dp[i + 1] + |h[i] - h[i + 1]|, & \text{其他情况} \end{cases} $$

初始条件：

$dp[n] = 0$

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::min;
using std::abs;
using std::vector;

int main() {
    int n;
    cin >> n;

    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];

    vector<int> dp(n + 1);
    dp[n] = 0;
    for (int i = n - 1; i >= 1; --i) {
        if (i + 2 <= n) {
            dp[i] = min(dp[i + 1] + abs(h[i] - h[i + 1]), dp[i + 2] + abs(h[i] - h[i + 2]));
        } 
        else dp[i] = dp[i + 1] + abs(h[i] - h[i + 1]);
    }

    cout << dp[1] << '\n';

    return 0;
}