字节跳动 动态规划
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
链接：https://leetcode-cn.com/problems/coin-change

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

动态规划

/*
和爬楼梯一个思想。 最后一枚拿的是1的时候，加上之前的最小数。 最后一枚拿的是2的时候，加上之前的最小数。最后一枚拿的是5的时候，加上之前的最小数。
凑成面值为 11 的最小数可以由以下 33 者的最小值得到：
1、凑成面值为 10 的最小数 + 面值为 1 的这一枚；
2、凑成面值为 9 的最小数 + 面值为 2 的这一枚；
3、凑成面值为 6 的最小数 + 面值为 5 的这一枚；
即 dp[11] = min (dp[10] + 1, dp[9] + 1, dp[6] + 1)。 //代码通过for循环实现

状态数组：dp[amount] 总价值为amount的时候的最小组合数
dp[amount] = min(dp[amount - coins[i]]) + 1 i in for [0, len - 1] if coins <= amount
条件：
1、首先的面值首先要小于等于当前要凑出来的面值；
2、2、剩余的那个面值应该要能够凑出来，例如：求 dp[11] 需要参考 dp[10] ，如果不能凑出来的话，dp[10] 应该等于一个不可能的值，可以设计为 11 + 1，也可以设计为 -1 ，它们的区别只是在具体的代码编写细节上不一样而已。
再强调一次：新状态的值要参考的值以前计算出来的「有效」状态值。这一点在编码的时候需要特别注意。
/

  1. class Solution {
  2. public:
  3.     int coinChange(vector<int>& coins, int amount) {
  4.         int len = coins.size() - 1;
  5.         vector<int>dp(amount + 1, amount + 1); //给0占位  // 注意：因为要比较的是最小值，这个不可能的值就得赋值成为一个最大值
  6.         dp[0] = 0;
  7.         for (int i = 1; i <= amount; i++) {
  8.             for (int coin : coins) {
  9.                 if (coin <= i) {        //新状态的值要参考的值以前计算出来的「有效」状态值
  10.                     dp[i] = min(dp[i], dp[i - coin] + 1);
  11.                 }  
  12.             }
  13.         }
  14.         return  dp[amount] == amount + 1 ? -1 : dp[amount];
  15.     }
  16. };