class Dynamic {

  public static int change(int amount, int[] coins){
    int[][] tab = new int[amount+1][coins.length+1];

    for(int i = 0; i <= amount; i++) 
      tab[i][coins.length] = Integer.MAX_VALUE;
    for(int j = 0; j < coins.length; j++)
      tab[0][j] = 0;
    
    for(int i = 1; i <= amount; i++) {
      for(int j = coins.length-1; j >= 0; j--) {          
        if (i < coins[j]) tab[i][j] = tab[i][j+1];
        else {
          int c1 = tab[i][j+1];
          int c2 = 1 + tab[i-coins[j]][j];
          if (c1 < c2) tab[i][j] = c1;
          else tab[i][j] = c2;
        } 
      }
    }
    return(tab[amount][0]);
  }
}