322. Coin Change

coinchane.js

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    
    // Using the greedy method. (Finding the maximum benefit.)
    // 1. First, we should select the maximum denomination.
    // 2. then, we should select the second largest coin.
    // 3. Finally, you can find the fewest number of coins.
    
    // 考慮
    // 1. [1,2,6,4] 這種 coins 沒有排列
    // 2. 如果直接從最大的 coins 那來，但如果是 [2,3,5] 11 這種案例，直接用 5 來找，會變成無法整除。
    // 總結上面使用 greedy 的缺點，不用他。
    
    //let result = 0;
    //coins.sort((a,b) => a > b);
    
    //for (var i=coins.length-1; i>=0 ; i--){
      //  let coinNum = Math.floor(amount/coins[i]);
      //  result += coinNum;
      //  amount -= coins[i] * coinNum;
      //  console.log(`coin:${coins[i]} ,coinNum:${coinNum}, amount:${amount}`);
    //}
    
    //return (amount === 0) ? result : -1;
    
    // DP
    // 從 sum 0 開始往上加
    // 每一次算好 sum 時就將要完成這個 sum 的總數所需的最小硬幣數存在 cache 中。
    // 每一次計算時，先用 sum - coin 去看看 cache 有沒有值
    // 有值就取出來用，如果沒有就代表無法用這個 coin 來處理。
    
    let cache = [];
    let sum = 0;
    cache[0] = 0;
    
    if(amount === 0){
        return 0;
    }
    
    coins = coins.filter((val) => {
        return (val <= amount) ? true : false;
    })
    
    while (++sum <= amount){
        let min = -1;
        for (var i=0;i< coins.length;i++){
            if(sum < coins[i]) continue;
                  
            if(cache[sum-coins[i]] !== undefined){
                let temp = cache[sum-coins[i]] + 1;
                min = (min < 0) ? temp : Math.min(temp,min);  
            }
        }
        if(min !== -1){
           cache[sum] = min; 
        }
    }
    return cache[amount] ? cache[amount] : -1;
};