digit dp

digit dp について書く。ここでは $n$ 以下の自然数の総数を求める問題を扱う。明らかに答えは $n+1$ だけど、見方を変えて解いてみれば、digit dp の本質がみえると思って書いてみた。

$n=31415$ として樹形図で列挙すると次のようになる。

f:id:pekempey:20180901194114p:plain

最も下のノードたちだけが変わった振る舞いをしていて、その他はすべて 10 通りの枝分かれを持っている。つまり2通りの振る舞いがあるので、同じ振る舞いをするものをまとめて扱えばもっとコンパクトに列挙できる。

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