518. Coin Change II

518. Coin Change II

 

https://hyunkookim.tistory.com/279

Knapsack 문제(배낭 문제) : DP 최적화

 

Knapsack 문제와 동전 문제의 유사점

• Knapsack 문제와 동전 문제는 모두 조합 최적화 문제이며, 동적 계획법(DP)을 사용해 해결합니다.
• Knapsack 문제:
  • 최적의 가치를 찾는 것이 목표.
  • 각 물건의 가치와 무게가 있음.
• 동전 문제:
  • 주어진 금액을 구성하는 조합의 수를 찾는 것이 목표.
  • 각 동전은 무게 대신 고유의 값(denomination)을 가짐.

 

• Knapsack 문제는 배낭의 용량 제약 조건을 만족하면서 물건의 가치를 최대화하는 문제입니다.
• 동전 문제와 Unbounded Knapsack 문제는 동전의 무한 사용 가능성에서 유사하며, DP 점화식을 활용해 효율적으로 풀 수 있습니다. 🎯

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        """
        동전 조합 문제를 해결하기 위한 점화식:
        dp[i] = dp[i] + dp[i - coin]

        점화식의 의미:
        - dp[i]: 금액 i를 만들 수 있는 동전 조합의 개수.
        - dp[i - coin]: 현재 동전을 사용하여 금액 i를 만들 때, 금액 (i - coin)을 만드는 경우의 수.
        - dp[i] += dp[i - coin]: 현재 동전으로 새로운 조합을 추가하여 dp[i]를 갱신.

        Recurrence relation:
        dp[i] = dp[i] + dp[i - coin]

        Explanation of the recurrence:
        - dp[i]: The number of combinations to make the amount i.
        - dp[i - coin]: The number of combinations to make the amount (i - coin).
        - dp[i] += dp[i - coin]: Updates dp[i] by adding the number of ways to make (i - coin), considering the current coin.
        """
        # DP 배열 초기화
        # Initialize DP array
        dp = [0] * (amount + 1)
        dp[0] = 1  # 금액 0을 만드는 방법은 아무 동전도 사용하지 않는 1가지
                  # There is one way to make amount 0, by using no coins.

        # 각 동전에 대해 DP 배열 갱신
        # Update DP array for each coin
        for coin in coins:
            for i in range(coin, amount + 1):
                # 점화식 적용: dp[i] = dp[i] + dp[i - coin]
                # Apply the recurrence: dp[i] = dp[i] + dp[i - coin]
                # - dp[i - coin]: 현재 동전을 추가하기 전의 경우의 수
                #                 Combinations before adding the current coin.
                # - dp[i]: 기존 dp[i]에 현재 동전을 추가하여 새로운 조합의 경우의 수를 누적
                #           Accumulate the new combinations using the current coin.
                dp[i] += dp[i - coin]

        # 금액 amount를 구성할 수 있는 총 경우의 수 반환
        # Return the total number of combinations for the given amount
        return dp[amount]

 

Unbounded Knapsack 문제

https://youtu.be/Mjy4hd2xgrs?si=zQoozi63_Nf8c1Ig

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        cache = {}

        def dfs(i, a):
            """
            dfs(i, a) 함수
            - i: 현재 고려 중인 동전의 인덱스
            - a: 현재까지의 금액 합계
            - 반환: 인덱스 i부터 시작해서 금액 a를 채우는 모든 가능한 조합의 수

            """
            if a == amount:
                return 1
            if a > amount:
                return 0
            if i == len(coins):
                return 0
            if (i, a) in cache:
                return cache[(i,a)]

            """
            dfs(i, a+coins[i])
            - 현재 동전(coins[i])을 사용하여 금액을 채우는 경우
            - 다시, 같은 동전을 사용할 수 있으므로 i는 그대로 유지
            - 현재 동전 사용 후 금액이 증가하므로 a + coins[i]로 금액을 업데이트
            
            dfs(i+1, a)
            - 현재 동전을 사용하지 않고 다음 동전(i+1)으로 넘어가는 경우
            - 동전 인덱스만 i+1로 증가
            - 금액은 변하지 않으므로 a는 그대로 유지            
            """
            cache[(i, a)] = dfs(i, a+coins[i]) + dfs(i+1, a)
            return cache[(i, a)]

        return dfs(0,0)

 

더 빠르게

 

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

        for a in range(1, amount+1):
            for i in range(len(coins) -1, -1, -1):
                dp[a][i] = dp[a][i+1]
                if a - coins[i] >=0:
                    dp[a][i] += dp[a-coins[i]][i]
        return dp[amount][0]

 

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

        for i in range(len(coins)-1, -1, -1):
            for a in range(1, amount+1):
                if a-coins[i] >=0:
                    dp[a] += dp[a-coins[i]]
        return dp[amount]

 

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

        for coin in coins:
            for a in range(1, amount+1):
                if a-coin >=0:
                    dp[a] += dp[a-coin]
        return dp[amount]

 

loop 가 coins -> amount 순서 이면,

- coin의 중복 조합은 1개로 고려하는 코드로 되고

- (2,1,1), (1,2,1), (1,1,2) => 1개로..

 

loop 가 amount -> coins 순서 이면,

- coin의 중복 조합은 여러개로 counting

- (2,1,1), (1,2,1), (1,1,2) => 3개로..