AtCoder DPの例題といてみた2

今回の問題

問題文

整数 $N$ が与えられます。次の条件を満たす長さ $N$ の文字列の数を $10^9 + 7$ で割った余りを求めてください。

• A, C, G, T 以外の文字を含まない。
• AGC を部分文字列として含まない。
• 隣接する $2$ 文字の入れ替えを $1$ 回行うことで上記の条件に違反させることはできない。

注記
文字列 $T$ の部分文字列とは、$T$ の先頭と末尾から $0$ 文字以上を取り去って得られる文字列です。
例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。

制約

• $3 \leq N \leq 100$

回答

#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][j][k][l]: iは現在の文字列の長さ、ｊは3つ前の文字kは: 2つ前の文字、lは1つ前の文字
遷移：長さ $i$ の状態で、文字 $j, k, l$ で終わっているとき、次に新しい文字を追加できるかを判定する。

判定には $j, k, l$ と new の4文字を使います。問題なければ dp[i+1][k][l][new] に加算します。