嘘っぽいDPをするときの一般的なテク

計算量的に嘘っぽいDPをするときのテクニック

$1$ 選です。ただしこの

$1$ は

$10$ 進法とは限りません。

連想配列を使う

メリット

• 実はこの添字が他の添字の内容から求められて～、みたいなときにその添字を残しても計算量を落とさずにできる
  • 使わない添字があるときは無意味なうえに連想配列で計算量が減らないことがあるので消す
• 実は有効な範囲だけ見ると計算量を削減できて～、みたいなときに実際に計算量を削減できる
  • 遷移にもそういう制約があると無意味なのでそっちは真面目にやる

デメリット

• 無駄に
  $\log$ や定数倍がかかる
  • AR/GCのWriterはみんな優しいのでこれくらいは見逃してくれる
  • 高速な言語を使っておく
  • 落ちたら考察しなおせばいい

まとめ

通るか自信がないときはとりあえず連想配列に放り込もう！

なんでこんなのかいたの

わたしがしらなかったから

タイトル詐欺？

タイトル詐欺です。

は

るく

ねむたい

おわりです。

期末終わってつかれた