js编程题：砝码最小数量问题

Question

假设有三种重量的砝码，2g、3g、7g，对于任意重量物品，请设计一个函数getResult(weight)，接收一个参数weight，返回所需砝码的最小数量。

输入示例：
const weight = 100;

输出示例：
getResult(weight) // 15 其中7g的14个，2g的1个

Answer 1

动态规划问题：

function getResult (weights, amount) {
    var memo = {};

    function dp (n) {

        if (memo[n]) return memo[n];

        //  base case
        if (n == 0)
            return 0
        if (n < 0)
            return -1
        // # 求最小值，所以初始化为正无穷
        var res = Infinity;
        for (let weight of weights.values()) {
            subproblem = dp(n - weight)
            // # 子问题无解，跳过
            if (subproblem == -1)
                continue
            res = Math.min(res, 1 + subproblem)
        }
        res = res === Infinity ? -1 : res;
        memo[n] = res = res === Infinity ? -1 : res;
        return memo[n];
    }

    return dp(amount)
}