题目链接

LeetCode

题目描述

给定不同面额的硬币 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

示例 4：

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

示例 5：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

    解题思路

    动态规划

    完全背包问题，且必须取到amount值
    可设每个面额的权重为1，求最小权重。
    转移公式由dp[i] = max(dp[i],1+dp[i-c])变为dp[i] = min(dp[i],1+dp[i-c]);
    完全背包问题不涉及顺序的完全背包问题，nums和target在内外循环都可以，但建议nums外循环，target内循环。下面num在外。
    涉及顺序（组合问题求排列数）的target在外，如爬楼梯问题
    image.png
  1. class Solution {
  2. public:
  3.     int coinChange(vector<int>& coins, int amount) {
  4.         vector<int> dp(amount+1,amount+1);
  5.         dp[0] = 0;
  6.         for(const int c : coins){
  7.             for(int i=1;i<=amount;i++){
  8.                 if(i-c>=0){
  9.                     dp[i] = min(dp[i],1+dp[i-c]);
  10.                 }
  11.             }
  12.         }
  13.         return dp[amount] == amount+1?-1:dp[amount];
  14.     }
  15. };
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int MAX = amount + 1;
        // Arrays.fill(dp, MAX);
        int sz = coins.length-1;
        for(int i = 1; i <= amount; ++i){
            dp[i] = MAX;
            for(int j = sz; j >= 0; --j){
                if(i - coins[j] >= 0 && dp[i - coins[j]] != MAX){
                    dp[i] = Math.min(dp[i],dp[i - coins[j]]+1);
                }
            }
        }
        return dp[amount] == MAX ? -1 : dp[amount];
    }
}
  • 时间复杂度 O(Sn) :其中 S 是金额，n 是面额数
  • 空间复杂度 O(S)