動的計画法（応用）辞書で状態を管理, bitで状態を管理

これはdictによって状態を管理することでコードを書きやすくしたり、計算量を最適化するテクニックです。