公開日 :
更新日 :
「先頭から\(1\)つずつ選んでいく。でも、次の選択に影響するのは直前のちょっとした情報だけ」という問題を、 dp[i][状態] で解くDP。
全部の選び方(\(2^N\)や\(3^N\))を調べる代わりに、「\(i\)番目まで決めて、いま状態\(s\)である」ものを\(1\)つにまとめる。
計算量は N × 状態数 × 遷移の数。