SRM 331 div1 level2 Shopping

解説もいいけど、賢過ぎなきがする。

Sドルまでn個のコインで表現できた状態で、x<=S+1の金額のコインを持ってくるとS+xドルまでn+1個のコインで表現できる状態に飛べる、というもの。１～Ｓまでは仮定から既にＯＫで単純に０、１～Ｓのそれぞれの金額にxを足すとx、x+1～Ｓ+xまでもＯＫになる。x<=S+1だから１～Ｓとx～S+xは繋がるという仕組み。 i=１～Ｘ（Ｘ含まず）のループで、i=1の時にコインの数c=1とする。i+1以下ので最大のコインを加える。コインに1があること前提で必ず加えられるコインはある。そのコインがkだとすると、i=i+k、c++でループの頭に戻る。つまり、iまでの金額をcコインで表現できるという意味。iがＸかＸを越えた地点でのcが欲しいので、i=Xの時に加算のループをする必要はない。 基本に返って考える。ナップサック問題だと思うとどうだろうか。andrewztaの回答が基本に忠実で美しい。

1. メモライズするmemはなんであるかを考える。ナップサック問題に習うと
   int[][] mem = new int[values.length][X+1];
   (金額をそのまま添え字にするために１～Ｘを利用）
   
   
2. 答えはreturn mem[values.length-1][X]で返したい。そう思えばmemの意味は
   「mem[i][j]はコイン種類0～iまでを使って金額1～jまでを表現するのに必要なコイン数」
   となる。
   
   
3. 各コインの枚数が問題なので、金額の小さいコインから順に何枚必要かを考えていく。
   金額xを作るのに金額vのコインは０～x/v個使用出来る。
   k個使用した場合、v, 2v, ..., kvの金額は表現できるので、１～xの全てを表現するには隙間を埋めなければならない。隙間はそれぞれの間隔mv+1～mv+v-1と、kv+1～xである。これは、1～v-1と1～x-kvが既に小さい金額のコインで表現できていれば良い。大きい方で十分なので１～max（v-1, x-kv）が表現できているかを調べる。
   
   
4. すると、k=0～x/vのループでmem[i-1][max(v-1, x-kv)]が既に値を持っていればmem[i-1][max(v-1, x-kv)]+kがmem[i][x]の候補になる。
   
   
5. ただし、添え字となるmax(v-1, x-kv)が0-Xであることを保障しなければならないのでmin(max(v-1,x-kv),x)となる。１～xが表現できていれば十分である。また、i-1も0-values.lengthなので、iは１から始めて、初期条件mem[0][j]は自明であるjを代入しておく。ここではソートされたvaluesの最初の要素が1であると仮定している。1でない場合は１を表現できないので-1を返して終了できるのでこの仮定は成り立つ。
   
   
6. mem[values.length-1][X]が答え。
   

public class Shopping {
public int minNumber(int X, int[] values) {
 Arrays.sort(values);
 int n = values.length;
 int[][] a = new int[X + 1][n + 1];
 for (int i = 1; i <= X; i++) {a[i][0] = -1;}
 for (int j = 1; j <= n; j++) {      
  for (int i = 1; i <= X; i++) {
   a[i][j] = -1;
   int v = values[j - 1];
   for (int k = 0; k <= X / v; k++) {
    int z = Math.max(i - k * v, v - 1);
    z = Math.min(z, X);
    if (a[z][j - 1] == -1) {continue;}
    if (a[i][j] == -1 || a[i][j] > a[z][j - 1] + k) {
     a[i][j] = a[z][j - 1] + k;
    }
   }
  }
 }
 return a[X][n];
}
}