leetcode 链接：零钱兑换

题目

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

示例：

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

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

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

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

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

解答 & 代码

动态规划：
设置动态规划数组 dp，dp[i] 存储的是凑成总金额 i 需要的最少的硬币个数
状态转移方程：

• n 是硬币种数（coins 数组的长度），coins[j] 是第 j 种硬币面额
• 这个状态转移方程的意思：我们在凑到总金额 i 的过程中，如果最后一枚硬币的金额是 coins[j]，那么将总金额 i 减去这枚硬币的金额，要凑成金额 i-coins[j] 需要最少的硬币个数为 dp[i-coins[j]]，如果这个值不为 -1（也就是没法凑到金额 i-coins[j] ），将这个值再加 1，就是凑到总金额 i 且最后一枚硬币金额是 coins[j] 时需要的硬币数。遍历所有面额的硬币作为最后一枚，计算所需硬币数，取最小值即可
• 特殊情况：dp[0] = 0, dp[负数] = -1

设要凑到的总金额为 A，硬币面额种类为 n

• 时间复杂度：O(An)
• 空间复杂度：O(A)

  class Solution {
  public:
    int coinChange(vector<int>& coins, int amount) {
        // 动态规划数组，dp[i] 存储的是凑成总金额 i 需要的最少的硬币个数
        // 需要计算 dp[0] ~ dp[amount]，因此数组长度 amount + 1。初始化为 -1
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;        // 如果金额为 0，最少需要 0 枚硬币
        // 计算 dp[0] ~ dp[amount]，即各个总金额 i 需要的最少的硬币个数
        for(int i = 1; i <= amount; ++i)
        {
            // 遍历每个硬币面额 coins[j]，以其作为凑成总金额 i 的最后一枚硬币，计算需要的硬币数
            for(int j = 0; j < coins.size(); ++j)
            {
                if(i - coins[j] >= 0 && dp[i - coins[j]] != -1 && (dp[i] == -1 || dp[i - coins[j]] + 1 < dp[i]))
                    dp[i] = dp[i - coins[j]] + 1;
            }
        }
        return dp[amount];
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：160 ms, 在所有 C++ 提交中击败了 11.31% 的用户 内存消耗：14.1 MB, 在所有 C++ 提交中击败了 23.69% 的用户

略作修改：dp数组初始化为 `INT_MAX`
```cpp
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i)
        {
            for(int j = 0; j < coins.size(); ++j)
            {
                if(i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX && dp[i - coins[j]] + 1 < dp[i])
                    dp[i] = dp[i - coins[j]] + 1;
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

执行结果：通过

执行用时：116 ms, 在所有 C++ 提交中击败了 34.10% 的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了 41.62% 的用户