LeetCode 322 零钱兑换

322.零钱兑换

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

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

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

示例：

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

动态规划

不同于518.零钱兑换II，此处需要求解的是，使用最少的硬币个数得到整数 amount ，此处的硬币数量是无限的。此处是一个组合问题，不存在选取顺序的问题。将之转化为完全背包问题：背包的容量为 amount ，物品的重量为 coins ，每一个物品的价值都为1，此处求解的是物品的最小价值。但是，此处的不同点在与，在向背包中装入物品时，要求将背包恰好装满。

1. 动态规划数组的定义：定义动态规划数组 dp[amount+1] 表示将 amount 装满所需的最少硬币个数。

2. 动态规划数组的推导：在第 i 次迭代中，在硬币 0-i 中进行选择，那么主要是 coins[i] 的选择问题。此处在进行递推时，需要考虑到可行的条件。首先是 dp[j] 的值，若是 dp[j]=-1 说明之前不存在方案将之装满，那么就需要查看 dp[j-coins[i]] 的值是否为 -1 ，若是为说明当前依旧无法装满，不修改值，负责当前存在从 dp[j-coins[i]] 的基础上将之装满的方案，对应需要的最少硬币数就是 dp[j-coins[i]]+1 ，若是 dp[j]!=-1 ，说明当前就存在可以装满的方案，那么尝试装入 coins[i] 看能否更少，当然需要 dp[j-coins[i]]!=-1 ，那么总体的推导过程就是：

if(dp[j]!=-1){
    if(dp[j-coins[i]]!=-1)
        dp[j]=min(dp[j],dp[j-coins[i]]+1);
}else{
    if(dp[j-coins[i]]!=-1)
        dp[j]=dp[j-coins[i]]+1;
}

1. 动态规划数组的初始化：在初始时全部初始为 -1 表示不存在装满的方案，而对于 dp[0] 装满0的背包，只需要0个硬币，初始化为 dp[0]=0

2. 动态规划数组的遍历顺序：此处先遍历物品，再遍历背包，并且在对背包遍历时从前向后遍历。

3. 举例验证： coins = [1, 2, 5], amount = 11 那么动态规划数组的推导过程为：

>
dp={0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11}
dp={0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6}
dp={0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3}

代码实现：

class Solution {
public:
        int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        vector<int> dp(amount+1,-1);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j]!=-1){
                    if(dp[j-coins[i]]!=-1)
                        dp[j]=min(dp[j],dp[j-coins[i]]+1);
                }else{
                    if(dp[j-coins[i]]!=-1)
                        dp[j]=dp[j-coins[i]]+1;
                }
            }
        }
        return dp[amount];
    }
};