公開日 :
更新日 :

状態を持つDP(dp[i][状態])

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

使える問題の目印

  • 各要素について少ない選択肢から\(1\)つ選ぶ(反転する/しない、表/裏、グー/チョキ/パー、食べる/食べる)。
  • 得点や条件が隣どうし(または直前の数個)だけ決まる。
    • 「\(i\) と \(i+1\) が ◯◯ なら \(+Y\)」「隣と同じではいけない」「連続\(K\)回までならOK」
  • 「お腹を壊している」「区間の中にいる」のようなモードがある。
  • \(N\) が \(2\times 10^5\) くらいで、全探索は無理。

コードを書く前に決める \(4\) つ