Frog 1 [Educational DP Contest / DP まとめコンテスト A]

https://atcoder.jp/contests/dp/tasks/dp_a

前提知識

• 最大最小系の動的計画法

解説

https://atcoder.jp/contests/dp/submissions/3946204

最小値のDPを書く。
dp[i] := i番目の足場にたどり着くためのコストの総和の最小値
最小値のDPを書く場合はすべての要素をinfで埋めておく必要がある。
　
dp[i]からの状態遷移はdp[i+1]とdp[i+2]なので、その2つへの遷移を書く。
dpを大きめにとっておくと、オーバーフローチェックをしなくて済む。

int N, H[101010], dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];
    
    rep(i, 0, N) dp[i] = inf;
    dp[0] = 0;
 
    rep(i, 0, N) {
        chmin(dp[i + 1], dp[i] + abs(H[i] - H[i + 1]));
        chmin(dp[i + 2], dp[i] + abs(H[i] - H[i + 2]));
    }
 
    cout << dp[N - 1] << endl;
}