[LeetCode] 518. Coin Change II

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

Coin Change II - LeetCode

문제 유형 : 다이나믹 프로그래밍 (동적계획법)

문제 난이도 : Medium

 

문제

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

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

 

동전 단위의 배열 coins가 주어집니다.

amount라는 금액이 주어집니다.

coins로 amount를 만들 수 있는 경우의 수를 구하시오.

정답은 32비트 정수의 범위가 나오도록 보장되어있고, 동전은 중복 사용가능하며, 배열 안에서는 중복되는 단위는 없습니다.

 

풀이

amount + 1의 크기만큼 dp 테이블을 만든다.

dp[i]는 i원을 만들기 위한 조합의 수이다.

 

1, 2, 5의 동전 단위를 사용할 때 dp[5]를 구하려면,

dp[4]의 조합에 1을 얹는 경우와, dp[3]의 조합에 2를 얹는 경우, dp[0]의 조합에 5를 얹는 경우가 있다.

그래서 이전의 dp테이블부터 채워주고, 테이블의 맨 끝을 반환하면 된다.

시간 복잡도 : O(m*n) (m = amount의 값 크기, n = coins의 배열 크기)

 

코드

C++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }
};

 

Python3

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] += dp[i-coin]

        return dp[amount]

 

Dart

class Solution {
  int change(int amount, List<int> coins) {
    List<int> dp = List<int>.filled(amount+1, 0);
    dp[0] = 1;

    for(int coin in coins){
      for(int i = coin; i <= amount; i++){
        dp[i] += dp[i-coin];
      }
    }

    return dp[amount];
  }
}

 

Java

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;

        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

 

Swift

class Solution {
    func change(_ amount: Int, _ coins: [Int]) -> Int {
        var dp = Array(repeating: 0, count: amount + 1)
        dp[0] = 1
    
        for coin in coins {
            for i in stride(from: coin, to: amount+1, by: 1) {
                dp[i] += dp[i - coin]
            }
        }
    
        return dp[amount]
    }
}