https://yukicoder.me/problems/no/636
前提知識
解法
https://yukicoder.me/submissions/231328
下から決める桁DPで解いていく。
メモ化再帰で書いていくと分かりやすい。
f(i, j) := [0,i]円+j円を支払うための最小枚数
当然f(N.length() - 1, 0)が答えになるわけだが、メモ化再帰の中身を詳しくコメントしていく。
「g[x] := x円を表現するための最小枚数」とする。
int f(int i, int j) { // =[0,i]円+j円を支払う最小枚数 if (i < 0) { iが負のときは全額支払い終わっているとき if(j == 0) return 0; j==0なら追加で支払う必要は無いので0 else return 1; j==1なら1円分だけまだ支払いが残っているので1 } if (0 <= memo[i][j]) return memo[i][j]; メモ化再帰用 int res = inf; rep(d, 0, 10) { d=[0,9]円分支払う事を考える int n = N[i] - '0' + j; 今の桁+jで支払うべき金額を出す int sm = g[d]; d円分支払うための枚数を出す if (d < n) sm += f(i - 1, 1) + g[10 + d - n]; もしd < nなら足りないので上の桁で補ってもらうことにする その為、上の桁での最小支払枚数をえる時にj=1としておく。 これで10円分+されるので10+dからnを引いたものがおつりになる。 これを足して必要枚数とする。 else sm += f(i - 1, 0) + g[d - n]; 足りているならそのままおつりを計算して、上の桁での最小枚数を求める。 chmin(res, sm); 10通り試してみて最小枚数を答える } return memo[i][j] = res; }
string N; //--------------------------------------------------------------------------------------------------- int g[11] = { 0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1 }; int memo[10101][2]; int f(int i, int j) { // =[0,i]円+j円を支払う最小枚数 if (i < 0) { if(j == 0) return 0; else return 1; } if (0 <= memo[i][j]) return memo[i][j]; int res = inf; rep(d, 0, 10) { int n = N[i] - '0' + j; int sm = g[d]; if (d < n) sm += f(i - 1, 1) + g[10 + d - n]; else sm += f(i - 1, 0) + g[d - n]; chmin(res, sm); } return memo[i][j] = res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, 10101) rep(j, 0, 2) memo[i][j] = -1; cout << f(N.length() - 1, 0) << endl; }