用語解説 - 桁DP

整数 $0$ 以上 $N$ 以下の整数で,ある条件を満たすものの数を求めるという時によく使われるDP.
ここで,ある条件とは,(多くの場合は)条件に各桁の数に関わることである.
上の桁から順番に処理していき,状態として(どの桁まで処理したか,今まで $N$ と一致しない桁を用いたか),および,問題特有の状態を付与して,その状態に対するパターン数などを計算する.
次の桁を決めるときに,$N$ と一致しない桁を用いていない場合は,$0$ から $N$ の対応する桁の数字までが取りうる.
$N$ と一致しない桁を用いた場合は,次の桁では全ての数字が来る可能性がある.

桁DPが出てくる問題


Current time: 2017年09月22日15時25分15秒
Last modified: 2014年05月24日04時16分45秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン: