LeetCode 322. 零钱兑换：_给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值,以及一个整数 targ

322. 零钱兑换

   

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

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

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思路：

利用dp：类似于LeetCode70：爬楼梯（唯一区别就是爬楼梯时：比如爬3层楼梯时，可能情况有1,1,1、1,2、2,1这三种，需要考虑顺序不同的情况。但是在零钱兑换中1,2和2,1属于同一种情况，不考虑顺序不同的情况）。此外，这里可以理解为：每次爬1,2,5阶楼梯层数~

i：表示当前要凑的金额

dp[i]：表示凑总金额为i时，所需的最少的硬币个数

硬币种类有三种：1、2、5元

（1）凑够的总金额为11时，需要找到总金额为10元(11-1)、9元(11-2)、6元(11-5)的情况

（2）凑够的总金额为10时，需要找到总金额为9元(10-1)、8元(10-2)、5元(10-5)的情况

（3）...

（4）一直到总金额为0元（图示）时停止，此时表示存在正好凑够amount（比如11）的总金额的组合

（5）找出其中所需的最少的硬币个数的组合，即可~

补充：

可使用BFS广度优先遍历求解：最先发现状态树中出现面额为0的解为最优解，其树的层数就是组合所需的最少的硬币个数

时间复杂度：O(m*n)  其中 m 是金额，n 是面额数。我们一共需要计算 O(m) 个状态，m 为题目所给的总金额

空间复杂度：O(m)     开辟长度为m的数组（如示例中的amount = 11）

Go版本：

// 类似于LeetCode70：爬楼梯，每次爬1,2,5阶楼梯层数
func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
 
    // 假设最小硬币面额为1，那么最坏情况下，达到amount金额则至少需要amount个面额为1的硬币，且最开始还有个dp[0]，故dp长度最大为amount+1
    max := amount + 1
    dp := make([]int, max) 
    dp[0] = 0
    for i := 1; i < max; i++ {
        // 只要初始化为大于 amount 的任意数都可以
        // 主要用于下面的min函数取最小值，且在最后return时可借此判断dp[amount]的值是否有被修改过
        dp[i] = max
    }
 
    // i代表当前要凑的金额数，从0逐渐递增至amount
    for i := 1; i <= amount; i++ { 
        // 分别选取coins数组中不同面额的硬币，找出其中最少的硬币个数
        // 例如示例1：选取硬币面额为1、2、5时，都对应不同的最少硬币个数，选取这其中硬币个数最少的一组结果
        for j := 0; j < len(coins); j++ {
            // 刚开始i代表的金额较小时，可能会导致 i-coins[j] 的值为负数，越界报错
            if i >= coins[j] {
                // 关键点：如果面额为 i-coins[j]的硬币不存在（无法正好拼凑）
                // 那么 dp[i-coins[j]] 的值就还是一开始初始化dp数组时大于amount的任意值，例如：dp[i-coins[j]] = amount+1。
                // 然后再通过min函数取较小值时，就可以排除掉 i-coins[j] 这种硬币面额不存在的情况。
                dp[i] = min(dp[i], dp[i-coins[j]] + 1) // +1：代表coins[j]自身所占的一个硬币数
            }
        }
    }
 
    // 若等于初始值amount + 1，则代表该记录未被修改过
    // 也就是最终不能正好拼凑为amount的dp[i]的值依然为初始化时的max值
    if dp[amount] == max {
        return -1
    }
 
    return dp[amount]
}
 
func min(a, b int) int {
    if a < b {
        return a
    }
 
    return b
}

C++版本：

// 类似于LeetCode70：爬楼梯，每次爬1,2,5阶楼梯层数
int coinChange(vector<int>& coins, int amount) {
    int Max = amount + 1;
    vector<int> dp(amount + 1, Max);            // dp下标: 需凑够的总金额(如1~11)；dp[i]: i=amount时组合使用的硬币数
    dp[0] = 0;                                  // 占位用，i下标从0开始（没有面额为0的硬币种类）
    for (int i = 1; i <= amount; i++)           // i：表示要凑的面值数：先找到amount为1的情况，进而求解amount=2...3...题目给定amount...
    {
        for (int j = 0; j < coins.size(); j++)  // 可能的面额：每次找出可能使用到的不同硬币情况
        {
            if (i >= coins[j])                  // 如果当前遍历到的金额i(1~11)大于当前面额(coins[j])，则计算个数 
            {
                // 状态方程：   
                dp[i] = min(dp[i], dp[i - coins[j]] + 1); // +1：coins[j]小于当前累计到达的金额数，可以使用该面额硬币(coins[j])，硬币个数+1
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]; // 因为开始时dp数组中所有值初始化为amount + 1，都大于amount；当状态数组dp[amount]也就是目标金额dp[11]不等于初始值时（说明初始值循环中被改动过），所以可以凑够dp[11]
    // return dp[amount] == amount + 1 ? -1 : dp[amount];   // 或者：dp[amount] = amount + 1(初始值)时，说明初始值循环中没被改动过，所以无法凑够总金额amount