digit dp

digit dp を説明する。過去に書いた記事では digit dp による複数の問題を扱っているが、この記事では最も基礎となる $n$ 以下の自然数の総数を求める問題のみを扱う。

https://pekempey.hatenablog.com/entry/2015/12/09/000603

明らかに答えは $n+1$ であるが、趣きを変えて計算してみようという訳である。digit dp で計算する場合には、以下のような樹形図が基本となる。ただしここでは $n=31415$ で考えている。

f:id:pekempey:20180901194114p:plain

同じ深さの状態を見てみると、黒で囲まれていない状態はそれ以下の樹形図の形が同じであることが分かる。以降同じような振る舞いをするのであれば纏めてよく、以下の DAG を用いた列挙に書き換えられる。

f:id:pekempey:20180901202452p:plain

ここまで分かると、動的計画法によって通り数を求める典型的な形になっていることが分かるだろう。実際に以下のように計算することができる。

f:id:pekempey:20180901202458p:plain


figure a: https://ideone.com/gKWStP
figure b: https://ideone.com/EVH2Yq
figure c: https://ideone.com/pbw9Vb