322. Coin Change

Solution 1: DP (Amount outer loop)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        minNumOfCoin2Amount = [0] + [0x7fffffff]*amount
        for amount in range(1, amount+1):
            for val in coins:
                if amount < val:
                    continue
                    
                # val <= amount, calculate the DP solution
                if minNumOfCoin2Amount[amount - val] != 0x7fffffff:
                    minNumOfCoin2Amount[amount] = min(minNumOfCoin2Amount[amount], 1 + minNumOfCoin2Amount[amount - val])
        
        ans = minNumOfCoin2Amount[amount]
        return ans if ans != 0x7fffffff else -1

Time Complexity: O(N^2) // Loop amount * len(coins) times
Space Complexity: O(N)

Solution 2: DP (Coins outer loop)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        minNumOfCoin2Amount = [0] + [0x7fffffff]*amount
        for coinVal in coins:
            for amt in range(coinVal, amount+1):
                if minNumOfCoin2Amount[amt - coinVal] != 0x7fffffff:
                    minNumOfCoin2Amount[amt] = min(minNumOfCoin2Amount[amt], 1 + minNumOfCoin2Amount[amt - coinVal])
        
        ans = minNumOfCoin2Amount[amount]
        return ans if ans != 0x7fffffff else -1

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 3: BFS

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        numOfCoin2AmountSolved = [True] + [False]*amount
        prevAns = [(0, 0)] # (numOfCoin, tgtAmount)
        while prevAns:
            (numOfCoin, prevAmount) = prevAns.pop(0)
            numOfCoin += 1
            for val in coins:
                newAmount = prevAmount + val
                if newAmount > amount:
                    continue
                elif newAmount == amount:
                    return numOfCoin
                
                # newAmount < amount
                if not numOfCoin2AmountSolved[newAmount]:
                    numOfCoin2AmountSolved[newAmount] = True
                    prevAns.append((numOfCoin, newAmount))
        return -1

Time Complexity: O(N^2)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/coin-change/discuss/778548/C%2B%2B-DP-solution-explained-~100-Time-100-Space
https://leetcode.com/problems/coin-change/discuss/77373/6-7-lines-2-ways
https://leetcode.com/problems/coin-change/discuss/77361/Fast-Python-BFS-Solution

Follow-up: Minimum Number of Operations to Convert Time