\(2^i\) 円紙幣がある世界で \(N\) 円の物を買うときに支払う紙幣とお釣りの合計枚数の最小値は, というお釣り問題になる.

下から \(i\) 桁目まで見たときに, その桁の数を払ったときの最小枚数 \(A(i)\) と上の桁に回したときの最小枚数 \(B(i)\) を DP で計算して最小枚数を求める.