AtCoder Educational DP Contest B問題解いてみた

今回の問題

$N$ 個の足場があります。足場には $1, 2, \dots, N$ と番号が振られています。
各 $i$ $(1 \le i \le N)$ について、足場 $i$ の高さは $h_i$ です。

最初、足場 $1$ にカエルがいます。カエルは次の行動を何回か繰り返し、足場 $N$ まで辿り着こうとしています。

• 足場 $i$ にいるとき、足場 $i+1, i+2, \dots, i+K$ のどれかへジャンプする。
• このとき、ジャンプ先の足場を $j$ とすると、コスト $|h_i - h_j|$ を支払う。

カエルが足場 $N$ に辿り着くまでに支払うコストの総和の最小値を求めてください。

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int k;
    cin >> k;
    int hlist[n];
    for (int i = 0; i < n; i++) {
        cin >> hlist[i];
    }
    int dp[n] ;
    for(int i = 0; i < n; i++) {
        dp[i] = 1e9;
    }
    dp[0] = 0;
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= k && i >= j; j++) {
            dp[i] = min(dp[i-j] + abs(hlist[i]-hlist[i-j]), dp[i]);
        }
    }
    cout << dp[n-1] << endl;
    
    return 0;
}

解説

A問題とほとんど変わらない。dp[i]をi段目まで行くときのコストの総和の最小値とすると、
dp[i] = min(dp[i-j] + abs(hlist[i]-hlist[i-j]), dp[i])(0 < j <k)となることがわかる。今回ももらうdpで書いた。