题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。
Problem:
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Idea:
DP /knapsack
Search
Solution1:
C++ / DP
Time complexity: O(n*amount^2)
Space complexity: O(amount)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 189 ms class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (auto coin : coins) { for (int i = amount - coin; i >= 0; --i) if (dp[i] != INT_MAX) for (int k = 1; k * coin + i <= amount; ++k) dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k); } return dp[amount] == INT_MAX ? -1 : dp[amount]; } }; |
Solution2:
C++ / DP
Time complexity: O(n*amount)
Space complexity: O(amount)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 16 ms class Solution { public: int coinChange(vector<int>& coins, int amount) { // dp[i] = min coins to make up to amount i vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int coin : coins) { for (int i = coin; i <= amount; ++i) if (dp[i - coin] != INT_MAX) dp[i] = min(dp[i], dp[i - coin] + 1); } return dp[amount] == INT_MAX ? -1 : dp[amount]; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
""" Author: Huahua Running time: 632 ms beats 90.27% """ class Solution: def coinChange(self, coins, amount): INVALID = 2**32 dp = [INVALID] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): if dp[i - coin] >= dp[i]: continue dp[i] = dp[i - coin] + 1 return -1 if dp[amount] == INVALID else dp[amount] |
Solution3:
C++ / DFS
Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Running time: 6 ms class Solution { public: int coinChange(vector<int>& coins, int amount) { // Sort coins in desending order std::sort(coins.rbegin(), coins.rend()); int ans = INT_MAX; coinChange(coins, 0, amount, 0, ans); return ans == INT_MAX ? -1 : ans; } private: void coinChange(const vector<int>& coins, int s, int amount, int count, int& ans) { if (amount == 0) { ans = min(ans, count); return; } if (s == coins.size()) return; const int coin = coins[s]; for (int k = amount / coin; k >= 0 && count + k < ans; k--) coinChange(coins, s + 1, amount - k * coin, count + k, ans); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
""" Author: Huahua Running time: 200ms """ class Solution: def coinChange(self, coins, amount): coins.sort(reverse=True) INVALID = 10**10 self.ans = INVALID def dfs(s, amount, count): if amount == 0: self.ans = count return if s == len(coins): return coin = coins[s] for k in range(amount // coin, -1, -1): if count + k >= self.ans: break dfs(s + 1, amount - k * coin, count + k) dfs(0, amount, 0) return -1 if self.ans == INVALID else self.ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment