桁DP練習メモ

はい。

練習に使った問題たち
AtCoder Beginner Contest 154　E - Almost Everywhere Zero
https://atcoder.jp/contests/abc154/tasks/abc154_e
Typical DP Contest　E - 数
https://atcoder.jp/contests/tdpc/tasks/tdpc_number
AtCoder Beginner Contest 007　D - 禁止された数字 https://atcoder.jp/contests/abc007/tasks/abc007_4
CODE FESTIVAL 2014 予選A　D - 壊れた電卓
https://atcoder.jp/contests/code-festival-2014-quala/tasks/code_festival_qualA_d

解いた順通りかな。多分。
大まかな方法を適当にメモ起こし。いつか綺麗に纏められるといいですね。
・紙とペンは最強の思考ツール。
・数えたいものに対応した配列をなんとなく考える。
・コードにすぐ起こせるような形式の配列が考えられないときは樹形図のような形式で考える。
・小さいケースのサンプルの結果と、紙とペンの計算結果が合うまで考える。
・とりあえず何よりNがどう遷移するか考える。
・紙とペンでの計算結果が合わないとコードにも起こせないと思います。多分。
・1以上N以下の整数で〜 などのNの先頭には0があることにする。
・ l=[int(i) for i in "0"+str(N)] とかで各桁ごとにint型でリストに入れておく。
・配列は大体 DP[桁数][Nと等しいか][条件を満たすか] という感じかな。言語や入力ケースによっては順番を変えたほうがいいことがあるかもしれない。
・Nと等しい数はNと等しい数、Nより小さい数は既にNより小さい数と1桁手前までNと等しかった数で最新の桁でNより小さくする(最新の桁が0の場合はNより小さい数は発生しなかったりする)。