leetcode：322. 零钱兑换

题目

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

示例：

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

解答 & 代码

动态规划：

  • 动态规划数组 **dp**：dp[i] 代表凑成金额 i 需要的最少的硬币个数
  • 状态转移方程：**dp[i] = min{dp[i - coin] + 1}**, coin ∈ coins
    • 针对金额 i，最后一枚硬币有 coins.size() 种选择，分别减去对应的币值得到剩余金额 i - coin。凑成剩余金额 i - coin 需要的最少的硬币个数为 dp[i-coin]，再加上一枚面值为 coin 的硬币，就凑成了金额 i

  • 初始化：dp[0] = 0，即凑成金额 0 需要 0 枚硬币

    1. class Solution {
    2. public:
    3.   int coinChange(vector<int>& coins, int amount) {
    4.       int size = coins.size();
    5.       if(size <= 0 || amount < 0)
    6.           return -1;
    8.       vector<int> dp(amount + 1, INT_MAX);    // 也可以初始化为 amount + 1
    9.       dp[0] = 0;
    10.       for(int i = 1; i <= amount; ++i)
    11.       {
    12.           for(int j = 0; j < size; ++j)
    13.           {
    14.               int coin = coins[j];
    15.               if(i - coin >= 0 && dp[i - coin] < dp[i] - 1)
    16.                   dp[i] = dp[i - coin] + 1;
    17.           }
    18.       }
    20.       return dp[amount] > amount ? -1 : dp[amount]; 
    21.   }
    22. };

    复杂度分析：

  • 时间复杂度 O(N)

  • 空间复杂度 O(N)

执行结果：

  1. 执行结果：通过
  3. 执行用时：60 ms, 在所有 C++ 提交中击败了 86.74% 的用户
  4. 内存消耗：14.1 MB, 在所有 C++ 提交中击败了 33.07% 的用户