322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:coins = [2], amount = 3
return -1.

Note:You may assume that you have an infinite number of each kind of coin.

使用DP的思想，从1块开始找到amount块

var coinChange = function(coins, amount) {
    if (amount===0)
        return 0;
    var num = coins.length;
    //表示当钱数为i时最少需要几个货币
    var dp = [0];
    //从钱数为1时开始
    for (let money = 1;money <= amount;money++) {
        //遍历每一种货币，找到money-coins[i]需要多少个货币
        for (let i = 0;i < num;i++) {
            //如果当前货币比钱数小
            if (coins[i]<money) {
                var remain = money-coins[i];
                var now = dp[remain]===undefined||dp[remain]===0 ? 0 : dp[remain] + 1;
                if (dp[money] === undefined) 
                    dp[money] = now;
                else {
                    if (now !== 0&&dp[money]!==0)
                        dp[money] = Math.min(dp[money],now);
                    else if (now !== 0&&dp[money]===0)
                        dp[money] = now;
                }
            } else if (coins[i] === money) {
                dp[money] = 1;
            }
        }
    }
    var res = dp.pop();
    return res === 0 ? -1 : res;
};