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

今回の問題

問題文
N個の足場があります。足場には 1,2,…,Nと番号が振られています。各 i(1≤i≤N) について、足場iの高さは hiです。

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

足場iにいるとき、足場i+1 またはi+2 へジャンプする。このとき、ジャンプ先の足場をjとすると、コスト∣hi−hj∣ を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    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++) {
        if(i >= 1) {
            dp[i] = min(dp[i-1] + abs(hlist[i]-hlist[i-1]), dp[i]);
        }
        if (i >= 2) {
            dp[i] = min(dp[i-2] + abs(hlist[i]-hlist[i-2]), dp[i]);
        }
    }
    cout << dp[n-1] << endl;
    
    return 0;
}

解説

dp[i]をi段目まで行くときのコストの総和の最小値とすると、
dp[i] = min(dp[i-1] + abs(hlist[i]-hlist[i-1]), dp[i-2] + abs(hlist[i]-hlist[i-2], dp[i])となることがわかる。今回はもらうdpで書いた。