動的計画法bit演算, 動的計画法, bitDP, DP, テーマ記事

ビットDPとは

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。

基本的には、以下のような DPを考えます。

\(dp\) := 部分集合 S に対して\(|S| ...

動的計画法DP, 桁DP, テーマ記事, 競プロ

競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。

桁DPとは

桁ごとに分けて考える動的計画法です。

「1からNまでの整数について、条件を満たす数はいくつあるか?」
「1からNまでの ...

動的計画法動的計画法, DP

動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。

普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアルゴリズムも、動的計画法を利用することで高速化 ...