题解 | #兑换零钱(一)#

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
function minMoney(arr, aim) {
    // write code here
    return dpResolve2(arr, aim);
}

/**
 * 暴力递归解法
 * 
 * 超时
 */

function resolve(arr, aim) {
    if (aim === 0) return 0;
    if (aim < 0) return -1;

    // 因为后续要和子问题比较大小，所以不能设置一个小值
    let res = Infinity;

    for (let i of arr) {
        // 计算子问题的结果
        const subProblem = resolve(arr, aim - i);
        // 子问题如果无解就跳过
        if (subProblem === -1) {
            continue;
        }
        // 在子问题中选择最优解，然后加1
        res = Math.min(res, subProblem + 1);
    }

    return res === Infinity ? -1 : res;
}

/**
 * 暴力解法优化 
 * 使用备忘录
 * 可以通过
 * 时间复杂度：O(KN)
 * 空间复杂度：O(N)
 */

function memoryResolve(arr, aim) {
    // 这里填充一个不可能出现的数
    const memory = Array(aim + 1).fill(-666);

    const helper = (arr, aim, memory) => {
        if(aim == 0) return 0;
        if(aim < 0) return -1;

        let res = Infinity;

        if(memory[aim] != -666) {
            return memory[aim];
        }

        for(i of arr) {
            const subProblem = helper(arr, aim - i, memory);

            if(subProblem === -1) continue;

             res = Math.min(res, subProblem + 1);
        }

        memory[aim] = (res === Infinity ? -1 : res);

        return memory[aim];
    }

    return helper(arr, aim, memory);
}

function dpResolve(arr, aim) {
    // 需要初始值为最大值，这里就不能填写 -666了，因为后面会有和前一个状态比较
    const dp = Array(aim + 1).fill(aim + 1);

    // Base Case
    dp[0] = 0;

    for(let i = 0; i < dp.length; i++) { // 先遍历容量
        for(let coin of arr) { // 再遍历物品
            if(i -  coin < 0) continue;

            dp[i] = Math.min(dp[i], dp[i-coin] + 1);
        }
    }

    return dp[aim] == aim + 1 ? -1 : dp[aim];
    
}

/**
 * 这题先遍历货币再遍历容量也是可以的
 */
function dpResolve2(arr, aim) {
    const fillValue = aim + 1;
    //dp[i]的定义：凑出货币i，最少需要dp[i]枚货币。
    const dp = Array(aim + 1).fill(fillValue);
    
    // Base Case
    dp[0] = 0;

    for(let coin of arr) {
        for(let i = 0; i < aim + 1; i++) {
            if(coin > i) continue; // 货币大于当前面值，无解跳过
            // dp[i] 递推公式
            dp[i] = Math.min(dp[i], dp[i -  coin] + 1);
        }
    }

    return dp[aim] === fillValue ? -1 : dp[aim];
}


module.exports = {
    minMoney,
};

细细品尝从暴力递归解法超时，到添加备忘录优化递归后通过，再到后面的动态规划迭代替换递归。