[Leetcode 518] Coin Change II

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

1) 코드

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(1, amount+1):
                if i-coin >= 0:
                    dp[i] += dp[i-coin]

        return dp[amount]

2) 해설

• 이 문제 같은 경우는 amount를 만들 수 있는 경우의 수를 구하는 문제다.
• 그런데 이 문제에서 중요한 점은 모든 '조합'을 구하는 것이 아니라
  '순열'에 해당하는 값을 구해야 한다는 것이다.
  -> 예를 들어, 1,2로 5를 만드는 경우의 수는
  조합인 경우는 1+1+1+2, 1+1+2+1, 1+2+1+1 .. 이런 식으로 다양하지만, 순열로 생각한다면 1+1+1+2, 1+2+2 이렇게 2가지만 가능하다
  
• 따라서 순열인 케이스를 구하기 위해서 기존의 Coin Change 문제와는
  다르게 for coin in coins라고 coins 리스트를 우선적으로 순회해준다.
  -> 이렇게 하면 항상 값이 작은 coin부터 더해지기 때문에
  비오름차순인 순열 케이스만 세는 것을 보장할 수 있다.