# 518. Coin Change 2

CYou are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

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

# Solution

Approach 1: DP with a 2D table. Let ways[i][v] be the number of ways to sum to v using the first i types of coin.

Approach 2: DP with a 1D table. Let ways[i] be the number of of ways summing to i dollars.

# Code (Python)

Approach 1:

    def change(self, amount: int, coins: List[int]) -> int:
        if not amount:
            return 1
        if not coins or amount < min(coins):
            return 0
        
        # ways[i][v]: number of ways to sum to v using the first i types of coin
        ways = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
        for i in range(len(ways)):
            ways[i][0] = 1
        for i in range(1, len(ways)):
            for v in range(len(ways[0])):
                # total ways = ways without using the latest type of coin + ways substituting the last values with the new type of coin
                ways[i][v] = ways[i-1][v]
                if v >= coins[i-1]: # note for coins[i-1] (not coins[i]) because we're talking about the first i types of coin
                    ways[i][v] += ways[i][v-coins[i-1]]
        return ways[-1][-1]

Approach 2:

    def change(self, amount: int, coins: List[int]) -> int:
        # Knapsack problem. ways[i]: num of ways for i dollars.
        # For each type of coin, total ways = num ways where the last coin dollars uses the coin + num ways where it doesn't use that coin.
        if not amount:
            return 1
        if not coins or amount < min(coins):
            return 0

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

        # first use just 1 type of coin, then use coins 1 and 2, etc
        for coin in coins:
            for value in range(coin, len(ways)):
                # add the number of ways where the last coin added was a coin with value='coin'
                ways[value] += ways[value-coin]
        return ways[-1]

# Code (C++)

Approach 1:

Approach 2: