零钱兑换

[Cosen95]

leetcode: https://leetcode-cn.com/problems/coin-change/

[Cosen95]

题目难度medium，涉及到的算法知识有动态规划。

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。

示例  1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明: 你可以认为每种硬币的数量是无限的。

思路分析

这道题目我们同样采用动态规划来解决。

假设给出的不同面额的硬币是[1, 2, 5]，目标是 60，问最少需要的硬币个数？

我们需要先分解子问题，分层级找最优子结构。

dp[i]: 表示总金额为 i 的时候最优解法的硬币数

我们想一下：求总金额 60 有几种方法？一共有 3 种方式，因为我们有 3 种不同面值的硬币。

• 拿一枚面值为 1 的硬币 + 总金额为 59 的最优解法的硬币数量。即：dp[59] + 1
• 拿一枚面值为 2 的硬币 + 总金额为 58 的最优解法的硬币数。即：dp[58] + 1
• 拿一枚面值为 5 的硬币 + 总金额为 55 的最优解法的硬币数。即：dp[55] + 1

所以，总金额为 60 的最优解法就是上面这三种解法中最优的一种，也就是硬币数最少的一种，我们下面用代码来表示一下：

dp[60] = Math.min(dp[59] + 1, dp[58] + 1, dp[55] + 1);

推导出状态转移方程：

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

其中 coin 有多少种可能，我们就需要比较多少次，遍历 coins 数组，分别去对比即可

代码实现

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(Infinity)
    dp[0] = 0;
    for (let i=0;i<= amount;i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i-coin]+1)
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
};