動的計画法

部分和問題とは、\(N\) 個の数 \( a_1, a_2, …, a_n\) が与えられたとき、その中からいくつかを選んで和をちょうど \(K\) にできるか判定をする問題です。

例えば配列が で、\(K\ ...

競技プログラミングでよく出題される木DPについての説明と、木DPで解ける一部の問題を同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固 ...

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。

区間DPとは

区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。

基本的には、以下のような DP ...

競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。

ビットDPとは

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

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

桁DPとは

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

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

動的計画法とは

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

以下のような特徴がありますが、抽象的なのでここではざっと眺 ...