AOJ2566 Restore Calculation

問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2566

問題概要
3つの整数A, B, Cが与えられる. これらの文字列には?が含まれるので, ?に0~9の任意の数字を入れた時A+B=Cが成り立つようなものは何通りあるか. 1e9+7で割った余りを出力する.

考えたこと
dp[i][j] := 下からi桁目までみて繰上りがあるときとないときの組合せの数をメモ化再帰で頑張る.
下の桁から見るので, 与えられた文字列は初めにreverseしておく.
A, B, Cのi番目が?か数字かで場合分けをするのでコード長が長くなるのは仕方なさそう, zero leadingは許されないので先頭桁を見ているときは0を除外する.

提出コード
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4921586

ずっとAOJをやっているので単発で出すより, まとめて書いた方がいいかもしれない