Friday, December 4, 2015

Coin change DP solution to keep track of coins

http://stackoverflow.com/questions/20185590/coin-change-dp-solution-to-keep-track-of-coins
``````public static int minimumNumberOfWays(int []deno, int amount){
int dp[] = new int[amount+1];
dp[0]=0;
int []prevCoin = new int[amount+1];
for(int j=1;j<=amount;j++){
dp[j]=Integer.MAX_VALUE;
for(int i=0;i<deno.length;i++){
if(deno[i]<=j && (1+dp[j-deno[i]] < dp[j]) ){
dp[j]=1+dp[j-deno[i]];
prevCoin[j]=deno[i];
}
}
}

int result = dp[amount];
for(int i=amount;i>=1;){
int j=i;
i=amount-prevCoin[i];
amount = amount - prevCoin[j];
}
System.out.println( Arrays.toString(coins)); ``````
You don't need the first dimension of your dp. You can use an array with only one dimension - the sum of all used coins. Then you can simply store the index of your last used coin for each state of your dp. What I mean is something like:
``````int[] dp = new int[n];
int[] usedCoin = new int[n];

for (int i=0; i < n; ++i) {
dp[i] = -1; // state not reached
usedCoin[i] = -1;
}

dp[0] = 0; // initial state -- we can have sum 0 without any coins
for (int coinId = 0; coinId < m; coinId++)
for (int sum = 0; sum + denom[coinId] < n; sum++) {
int newSum = sum + denom[coinId];
if (dp[newSum] == -1 || dp[newSum] > 1 + dp[sum]) {
dp[newSum] = 1 + dp[sum];
usedCoin[newSum] = coinId;
}
}``````
If you want to find a concrete decomposition with minimum amount of coins, you can do something like:
``````int sum = changeAmount;
System.out.println("The used coins are:");
while (usedCoin[sum] != -1) {
System.out.print(denom[ usedCoin[sum] ].toString() + " ");
sum -= denom[ usedCoin[sum] ];
}``````
Related: Coin change problem with limit on number of coins of each denomination