322. Coin Change

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def dp(n):
            if n == 0:
                return 0
            if n < 0 :
                return -1
            res = float('inf')
            for coin in coins:
                if dp(n-coin) < 0 :
                    continue 
                res = min(res,dp(n-coin)+1)
            return res if res != float('inf') else -1
        return dp(amount)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # time O(NM), N = amount M = len(coins) ; space O(S)
        # step1: create a memo 
        memo = {}
        def dp(n):
            # step 2: check if n in memo
            if n in memo:
                return memo[n]
            # step 0 : base case1 -- if n == 0 
            if n == 0:
                return 0
            #step 0.5 : base case2 -- if n < 0
            if n < 0 :
                return -1
            # step3: initialize current decision var
            res = float('inf')
            # step4: solve subproblem-- loop through choices 
            for coin in coins:
                sub = dp(n-coin) # cache dp(n-coin) to sub can optimize runtime 
                # step4.1: early determination n-coin < 0 ==> return -1
                if sub == -1 :
                    continue
                # step4.2 update curren decision:  compare change or no change 
                res = min(res,sub+1)
                
            #step5 update final changes 
            memo[n] = res if res != float('inf') else -1
            
            return memo[n]
        
        return dp(amount)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # time O(kN) space O(N), N = amount, k = len(coins)
        # space O(N)
        # dp[i]: each ammount need mininum changes 
        # why initialize value is amount + 1 ?  because at most can all be changed with $1 coin. 
        # step1: initialize dp max val 
        dp = [amount + 1]  * (amount + 1)
        # step2: base case 
        dp[0] = 0
        # step3: loop dp 
        for i in range(len(dp)):
            #step3.2  iterate choices
            for coin in coins:
                #step3.3 early termination
                if i-coin < 0:
                    continue
                # step3.4 find current minimun coin change best choice
                dp[i] = min(dp[i-coin] +1,dp[i]) 
        # step4 check if dp[amount] changed, return valid dp[amount]
        return dp[amount] if dp[amount] != (amount + 1) else -1

################# non shorten space version