LeetCode: Minimum Coin Change Denominations

/**
coin change combinations, find minimum coins requierd for a changed and also the denominations that can be used for the change
*/
public class MinimumCoinChangeDenominations{
static int[] coins;
//lets have the coins in sorted denomination order (i.e. increasing order)
static int change;
static int[] changes;
public static int coinChange(int num, int index){
if(index<0){
if(num<=0){
return 1;
}
return -1;
}
int withoutUsing = coinChange(num, index-1);
int using = coinChange(num - coins[index], index-1);
changes[num] = Math.min(using, withoutUsing);
return changes[num];
}

public static void main(String[] args){
change = 27;
coins = new int[]{1,2,5,10,25};
changes = new int[change + 1];
//initialize changes to default values
for(int i=0;i<changes.length; i++){
changes[i] = Integer.MAX_VALUE;
}
coinChange(change, 4);
int minChange = changes[change]!=Integer.MAX_VALUE?changes[change]:-1;
System.out.println(minChange);
}
}

No comments:

Post a Comment