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

背包问题

此题可视为背包问题，要兑换的钱数aim为背包容量，arr为各个物品的价值，最少需要arr中的几件物品才能装满背包。

如何转换为动态规划思路：DP数组应该存放什么？

题目要求的是最少需要多少张arr中的货币才能组成aim的钱数，可以自顶向下分析，组成aim-1的钱数最少需要多少张货币，... ，组成1的钱数需要多少张货币，组成0的钱数需要多少张货币。这样DP数组中存放的就是组成0-aim的目标钱数最少需要的货币数量。

最小子问题

• 可以从最简单的情况考虑，如果目标钱数是0，那么组成0的钱数需要0张货币，后面的钱数的最小货币数量都可以通过这个情况由小到大递推得到。
• 其次可以考虑特殊情况，比如但目标钱数和arr中的纸币金额一致时，只需要1张该金额的货币就可以组成该目标钱数。假设目标钱数为i，arr[j]对应的金额和i相等，此时拿出一张arr[j]组成目标钱数后，还剩下i-arr[j]=0的目标钱数，那剩下的目标钱数最少能兑换多少张纸币呢，即为dp[i-arr[j]=dp[0]=0，那么dp[i]能最少兑换的纸币数量等于一张arr[j]纸币加上dp[i-arr[j]]中最少能兑换的纸币数量，此时dp[i]=1+dp[i-arr[j]]=1。

如何思考状态转移方程？

要组成一个目标钱数为i的纸币，可以分析一下从arr中取出一张金额小于目标钱数i的纸币后，剩下的目标钱数还能兑换的最少纸币数量的情况。对于arr中不同的选取金额的情况，选出最小的一个，即为目标钱数为i的纸币所能得到的最少纸币数量，即dp[i] = min(dp[i-arr[j]], dp[i])，其中arr[j]小于i，且j在arr的金额种类数量范围内。

参考

https://www.bilibili.com/video/BV1cT4y1w7Ct/?spm_id_from=333.880.my_history.page.click

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
function minMoney( arr ,  aim ) {
    // write code here
    const dp = new Array(aim+1).fill(Infinity);  // dp存放目标钱数从0-aim分别最少可以兑换多少张arr中的纸币
    dp[0] = 0;  // 当目标钱数为0时，没有纸币可以兑换，可以兑换的纸币数量为0，根据这个初始状态递推到最终aim金额的所能兑换的最少纸币数量

    for (let i = 1; i <= aim; ++i) {
        // 对于目标钱数为i的背包，分别遍历各个物品，看哪个物品放入后可以塞满i的背包的物品数量最少
        for (let j = 0; j < arr.length; ++j) {
            if (arr[j] <= i) {  // 只有在arr[j]的面额小于等于目标钱数i时，才可以兑换一张arr[j]
                // dp[i-arr[j]]表示i的容量兑换完一张arr[j]的纸币后，剩下的目标钱数最少能兑换的纸币数量，+1表示一张arr[j]
                dp[i] = Math.min(dp[i], dp[i-arr[j]]+1);
            }
        }
    }

    // 遍历完成后，如果aim的目标钱数能够被arr中的所有纸币兑换，则dp[aim]会被更新，否则就是最大值，表示无法被兑换
    return dp[aim] === Infinity ? -1 : dp[aim];
}
module.exports = {
    minMoney : minMoney
};