leetcode-dp

322. Coin Change.py

class Solution:
    """
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative?
            1.should given amount is larger than 0
            2.there's no negatvie coins
            
    Thought Process:
        Brute Force [Backtracking]:
            Generate all possible combination whose amount is equal to given amount and return fewest number of coins to make up this amount.
            In this way, time complexity would become exponential.
        DP:
            Let's define our subproblem fewest number of coins to make up amount i, where  0<=i<=amount, soluve our sol to dp[i].
            
            So, our goal is to find dp[amount] and base case, when i=0, it's apparently we don't need any coine. So, dp[0] = 0
            
            Then, think about current subproblems dp[i] relies on every possible coin we can take dp[i-c], for c in coines, as long as i-c >=0.
            And formulation would be dp[i] = min (dp[i-c] + 1)
        
        Demo and Discuss your solution/thought process visually.
            -Use an example input that's simple and it does not have more than 4 elements.
            -expected output/answer
            -Our ouput: how to get the output from example input.
            
    Time complexity Analysis
    
    
    Test Case to run your algorithm manually
        -put # on each visited statement
        -write down actual val as a comment
           []
          / 
         1 10
       /
     1 9
     
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        Don't forget to simply describe brute force solution orally during the interview
        before getting started to use any algorithm technique.
        
        Brute force:
            Using complete search, we try to generte all possible combination of coins subject to amount S, and find out minimum number of coins out of them with amount.
            In worst case, we at most have 2 raise to power of n possibilities.
        
        However, it takes exponential time in n, n is number of coins. So, we use dp.
        
        T:O(n*S), where S is the amount and n is number of coins.
        S:O(S) because we use extra space for the memorization table.
        """
        MAX = float('inf') # because it is impossible to form a negative sum of money.
        dp = [0] + [MAX] * amount # base case: dp[0] = 0

        for i in range(1, amount + 1):
            # recursive formulation
            dp[i] = min([dp[i - c] + 1 if i - c >= 0 else MAX for c in coins])
        
        if dp[amount] == MAX:
            return -1
        else:
            return dp[amount]
        
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        T:O(n*amount)
        S: O(amount) since we store given amount solution to subproblems into dp table.
        """
        dp = [float("inf") for _ in range(amount+1)]
        dp[0] = 0
        for i in range(1, amount+1):
            for c in coins:
                if i-c>=0:
                    dp[i] = min(dp[i], dp[i-c]+1)
        
        return -1 if dp[amount] == float("inf") else dp[amount]
    
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        TLE
        T: O(2^n)
        S: O(amount) since in worst case, depth of recursion could be amount when there's coin whose denominations is 1.
        """
        def backtrack(s, t, nb):
            if t == 0:
                ans.append(nb)
                
            for i in range(s, n):
                if t-coins[i] < 0:
                    continue
                backtrack(i,t-coins[i], nb+1)
                
        n = len(coins)
        ans = []
        backtrack(0,amount,0)
        if len(ans) == 0:
            return -1
        else:
            return min(ans)