518. Coin Change 2

518. Coin Change 2

(https://leetcode.com/problems/coin-change-2/#/description)

---

amount 를 coins의 값들로 만들 수 있는 모든 경우의 수를 리턴하는 문제다. 원래는 coin들로 recursive 하게 빼주다가 0이 되면 리턴하게 하는 식으로 하려고 했는데, 빼주었던 coin들을 어떻게 가지고 있어야 할지 구현하는게 어려워서 포기했다.

결국 DP로 풀었는데, 2차원 배열로 어떻게 하려다가 잘 안되서 그냥 인터넷에서 보고 구현했다.

dp의 index값은 amount 값이 되고, 그렇기에 0원을 만들 수 있는 경우의 수는 1가지 (아무것도 없는 경우) 있기 때문에 dp[0] = 1 을 해준 상태에서 시작한다.

amount 5, coins = [1,2]로 보자면 (임의로 통화는 원이라고 지정하겠다.)

dp[1] 은 1원을 만들 수 있는 경우의 수가 담기는데 이 때 경우의 수는 1원만으로 만들 수 있는 경우의 수 하나 밖에 없다. 2원은 1원 보다 크기 때문에 1원을 만들 수 없다.

그래서 dp[1] = dp[1] 이 된다. 즉 계산할 필요가 없다.

dp[2]는 2원을 만들 수 있는 경우의 수 인데, 이때 2원을 만들기 위해선 1원으로 2원을 만드는 경우의 수 들에 대해 1을 다 더해주면 2가 되는 경우의 수가 되고 거기에 2로만 만들 수 있는 경우의 수가 들어간다.

즉 dp[2] = dp[2] (1원으로 2원을 만들었던 경우의 수) + 2원만으로 2원을 만드는 경우의 수 가 된다.

2원만으로 2원을 만드는 경우의 수는 1가지 밖에 없는데 이는 dp[0]과 같다. 왜냐면 현재 coin으로 현재 amount를 만들 수 있는 경우의 수는 언제나 1가지 이기 때문이다. 

더 보면 dp[3] = 1원으로만 3원을 만들었던 경우의 수 + 2원으로 3원을 만들 수 있는 경우의 수 이다.

첫번째 값은 dp[3]이 되고 두번째는 3원으로 2원을 만들려면 경우의 수는 한 가지 밖에 없는데 바로 dp[1] 인 것이다. 왜냐면 3원-2원는 1원이고 1원을 만들 수 있는 경우의 수는 1원 한가지 인데, 이 말인 즉슨 (2+1 or 1+2) 인 것이다.

4원 까지 보자.

4원을 만드는 경우의 수는 1로 4원을 만드는 경우의 수 (1가지) + 4원에서 1원을 뺀 값의 경우의 수 (3원을 만드는 경우의 수 2가지) 여서 3이 된다.

	0	1	2	3	4	5	amount
1	1	1	1	1	1	1	1원으로 만드는 경우의 수
1, 2	1	1	2	2	3	4	1원과 2원으로 만드는 경우의 수

식은 그래서 이렇게 된다.

dp[idx] = dp[idx] + dp[idx-coin]

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """

        dp = [0 for _ in range(amount + 1)]
        dp[0] = 1

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

        return dp[amount]