公式解説と同じく、$f(x) =$ （$x$ 以下の良い整数の個数）を求めることにします。

$dp_{i, j, k, l}$ = （$i$ 桁目まで決めて $0$ でない最初の数字が $j$ であり、$x$より小さいことが確定しているかどうか（$k$）と先頭から $0$ が続くかどうか（$l$））
の状態を持つ桁DPをすることで、$f(x)$ の値を求めることができます。

実装例（C++）
実装例（Nim）