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

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

桁DPとは

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

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

AtCoder動的計画法, 数え上げ, DP, 500点, 桁DP, 場合分け

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...