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; }