力扣：322. 零钱兑换（动态规划入门）

?链接：力扣：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

思路：

重述做题步骤 ：

1.重述问题：凑成总金额 amount 所需的最少的硬币个数，认为每种硬币的数量是无限的。

2.找到最后一步：选择某个硬币后刚好金额到 amount 。

3.去掉最后一步，变成了什么？

如实例1最后选择硬币5金额到达了 amount ，那么子问题变成了选择到某个硬币金额到达 amount -? 5。

4.边界：当amount为0时，不需要任何硬币来组合，所以 v[0] = 0

分析：因为动态规划遍历要明确数组元素中记录了什么样的数据，与寻常题不同，因为有金额的限制，不妨用当前达到的金额作为下标（而不是遍历coins数组），而其值作为硬币数。所以我们从 1 开始对金额进行遍历，如果当前金额大于硬币面值才进入子问题和本身最小值的取优，最后得出的 v[amount] 就是问题的答案。因为要取最小值，所以我们要将 v 初始化为1个很大的值。如果 v 元素值 >= 1e9，说明没有方案，返回-1。

代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
         vector<int> v(1e4+5,1e9);
         v[0]=0;//当amount为0时，不需要任何硬币来组合
         for(int i=1;i<=amount;i++){
             for(int j=0;j<n;j++){
                 if(i>=coins[j]){
                     v[i]=min(v[i],v[i-coins[j]]+1);
                 }
             }
         }
         return v[amount]>=1e9?-1:v[amount];   
    }
};