桁DP
まず上のやつを読めば良いと思います（丸投げ）
馬鹿でかい数字に対するDP。大体は、
「N以下の自然数で、〇〇なものは何通りあるか」か
「N以下の自然数で、〇〇を満たす最大の値を求めよ」
みたいな形をしています。N以下。
$ N \leqq 10^{500}みたいな感じで、とても制約が大きいことが多い。
実装
値はstringで持つ。i桁目の数はs[i] - '0'で取得できる。
dp[i桁目まで見た][既にn以下になることが確定しているか] 言い換えるとdp[桁][未満フラグ]
遷移を、未満フラグがtrueなら0~9まで考えて、falseなら0~D(i桁目の数)とする
dp[i + 1][j || d < D] = dp[i][j]みたいな感じ
考察する時は、それぞれの桁でどういう操作をするのかを先に考える（知らんが）
N以下が確定してるとは…？
例題