Frog 2 [Educational DP Contest / DP まとめコンテスト B]

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

前提知識

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

解説

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

EDPCのAの強化版であり、同じDPで同じ方針で解く。
dp[i] := i番目の足場にたどり着くためのコストの総和の最小値
最小値のDPを書く場合はすべての要素をinfで埋めておく必要がある。
　
遷移の個数を見ると、どの状態であっても最大でK通りある。
状態数がNで、遷移がKなので、全体でO(NK)なので間に合う。
DPで計算量見積もりをする場合は、O(状態数)*O(ある状態における遷移)で計算しよう。

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