엔지니어 게시판
LeetCode 솔루션 분류

[5/21] 322. Coin Change

작성자 정보

  • mingki 작성
  • 작성일

컨텐츠 정보

본문

[LeetCode 시즌 3] 2022년 5월 21일 문제입니다.

https://leetcode.com/problems/coin-change/ 


322. Coin Change
Medium
11188270Add to ListShare

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

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

관련자료

댓글 2

coderoncruise님의 댓글

  • coderoncruise
  • 작성일
dynamic programming - bottom up
- compute all minimum counts up to 'amount'
- TC: O(amount * N of coins)
- SC: O(amount) for memoization table

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], dp[a - c] + 1)
                    
        return dp[-1] if dp[-1] != float("inf") else -1

mingki님의 댓글

  • mingki
  • 작성일
C++
Runtime: 143 ms, faster than 39.70% of C++ online submissions for Coin Change.
Memory Usage: 14.3 MB, less than 73.09% of C++ online submissions for Coin Change.
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, 1e9);
        int n = coins.size();
        
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < n; ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};
전체 128 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


알림 0