桁DP

概要

「N以下の正整数で、〇〇を満たす数値の個数を求めよ」といった問題に使うDPアルゴリズムです。

最上位桁から1桁ずつ順に走査していき、

  • N未満が確定しているパターン
  • N未満が確定していないパターン

それぞれについてを数え上げていきます。
この「N未満が確定しているか」を未満フラグと言います。

例題

Almost Everywhere Zero (ABC154)

回答例

類題

参考