Mysterious Stairs [yukicoder No.533]

https://yukicoder.me/problems/no/533

解説放送

https://youtu.be/OSwsugwPij8?t=685

解法

https://yukicoder.me/submissions/183004

以下にもDPで解くような問題。
dp[i][j] := 階段のi段目にいて、直前にj段飛ばしで来た組合せ
これを更新する時は、
dp[i][j]からdp[i+1][1](j!=1)とdp[i+2][2](j!=2)とdp[i+3][3](j!=3)が更新できる
よくありそうな感じの問題。

舞葉さんの記事が最強
buyoh.hateblo.jp

int N;
mint dp[1010101][4];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    dp[0][0] = 1;

    rep(i, 0, N) rep(j, 0, 4) {
        rep(k, 1, 4) if(k != j){
            dp[i + k][k] += dp[i][j];
        }
    }

    mint ans = 0;
    rep(j, 0, 4) ans += dp[N][j];
    cout << ans.get() << endl;
}