Massive Algorithms: Coin change DP solution to keep track of coins

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148775&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目是这样的，输入是一个int amount 和 vector<int> coins，分别表示总货币量、各个coin的价值量，要求以最少的coin个数凑齐总货币量。（大家应该都熟悉吧？入门级的DP题目。。）
然后输出的是每种货币的数目，vector<int> nums。
举例： amount = 40, coins = [1,5,15,25]，输出[0,1,1,1]
再举例： amount = 40, coins = [1,5,20,25]，输出[0,0,2,0]

关键是刚开始没怎么听清楚，问了好几遍才确认，自己也是太紧张了。然后先确认了几个细节要求：
都是整数？是的
最后是要凑齐exact的目标数值amount？是的
会有无解的情况吗？默认总会有价值为“1”的coin

我刚开始想着用backtracking+贪心来做，先sort，再用最贵的coin开始凑，后来一想不对，应该bottom up用dp，转移方程就是dp = min(dp[i-1]+1, dp[i-coins[j]]+j) for all j from 1~coins.size()-1;

然后写着写着就迷糊了，忘记目标不是coin的总数而是每个coin的个数。。。事实上，我写完之后(当时是只记录dp，即总数)，他说yes I think this works. 然后follow up问如果amount很大怎么办。
我想着想着发现只要keep tracking dp 里后面 coins.size() 数量的dp即可，only store the dp, dp[i-coins[1]]....., dp[i-coins[coins.size()-1]]. more info on 1point3acres.com
他说好的，很好，又问了总体的时间空间复杂度。（好了到目前为止我们两个估计都忘记了刚开始要的是各个coin的个数。。。）

然后闲聊了几句，他突然问我，噢等一下，我们要求的不是总数。。。我就突然紧张了，想了一会后，在每个dp的循环里加了个stack用来记录插入过的coin index，如果dp更新的话就把前面
的那个pop出来回滚回去，再把新的弄进来，感觉好像可以。。。
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];
    List<Integer> coinsAdded = new ArrayList<Integer>();
    for(int i=amount;i>=1;){
        coinsAdded.add(prevCoin[i]);
        int j=i;
        i=amount-prevCoin[i];
        amount = amount - prevCoin[j];
    }
    Integer [] coins = coinsAdded.toArray(new Integer[coinsAdded.size()]);
    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] ];
}

Coin change DP solution to keep track of coins

Labels

Popular Posts