凑硬币

[chiyan-lin]

使用动态规划来算凑硬币的最小个数

给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：

// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);

子问题间互相独立，符合最优子结构，属于动态规划

dp[m] = min(dp[m], dp[m-v[i] ]+1)

m = 需要凑的钱数，dp[m]为凑到的次数，dp[m-v[i] ]+1 为 m-v[i]钱数凑到的次数

所以代码如下

自上而下

function coinChange(coins, amount) {
    function dp(n) {
        if (n == 0) return 0;
        if (n < 0) return -1;
        let res = Infinity;
        for (let i = 0; i < coins.length; i++) {
            const subproblem = dp(n - coins[i]);
            if (subproblem == -1) continue;
            res = Math.min(res, 1 + subproblem);
        }
        return res;
    }
    dp = memo(dp);
    return dp(amount);
}
function memo (fn) {
    const memoMap = {};
    return function (...arg) {
        const key = arg.toString();
        if (memoMap[key]) {
            return memoMap[key];
        }
        memoMap[key] = fn.apply(this, arg);
        return memoMap[key];
    };
}

console.log('coinChange;', coinChange([1, 3, 5, 8], 40));

自下而上

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for(let i = 0; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] < 0) continue;
            dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
        }
    }
    console.log('dp', dp);
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

console.log('coinChange; 5', coinChange([1, 3, 5, 8], 11));

---

动态规划详解 最少钱币数