leetcode-dp

518. Coin Change 2.py

class Solution:
    """
    Problem Clarificaitin:
        at least we have one coin to choose right?
        
    Thought Process:
         Brute Force[backtrackiing]
         
         DP:
            Let's define our subproblem total nb of combinations that make up amount j using fisrt i coin only , store sol to dp[i][j], where i <= len(coins) and j <= given amount
            
            Then, our main goal is to return dp[n-1][amount]
            
            base case when j == 0, dp[i][0] = 1
            
            The current subproblem dp[i][j] relies on whether we can use the ith coin to constuct j or not
                => dp[i-1][j](cannot't use ith coin )
                => dp[i-1][j]+dp[i][j-coins[i]] if j-coins[i] >= 0 (can use ith coint)
                
    Test case 
        dp table
            coins = [1, 2, 5] and amount = 5
            
          i\j 0 1 2 3 4 5
          0   1 1 1  -- > using fisrt coin only to construct 2. there's only 1 way 1+1 = 2
          1    
          2
          i\j 0 1 2 3 4 5
          0   1 1 1 1 1 1 using first coin only to construct 5. there's only 1 way 1+1+1+1+1 = 5
          1   1 1 -> relies on dp[1][1] since coins[1] > amount 1
          2
          
          i\j 0 1 2 3 4 5
          0   1 1 1 1 1 1 using first coin only to construct 5. there's only 1 way 1+1+1+1+1 = 5
          1   1 1 2 -> relies on dp[1][0] + dp[0][2]
          2
           ...
           
           Another case for len(coins) = 1
            coins = [2] and amount = 3
          i\j 0 1 2 3
          0   1 0 1 0 -> relies on dp[0][1] (impossible to make it since 2 + 1 = 3) but we don't ave coin 1 in our coins
    """
    def change(self, amount: int, coins: List[int]) -> int:
        """
        dp[i][j]: number of combinations to construct amount j with first i type of coins.
        
        T: O(n*amount)
        S: O(n*amount)
        """
        n = len(coins)
        if amount == 0:
            return 1
        # step1: base case
        dp = [[0 for col in range(amount + 1)] for row in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1
        # step2: recursive formulation
        for i in range(1, n + 1):
            for j in range(1, amount + 1):
                if j - coins[i-1] >= 0:
                    # we could either to use or not use i type. However, we can use i th coin as many times as we want.
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    # Because we cannot chose i th element to construct amount j, number of combinations to construct amount j with first i type of coins equal to number of combinations to construct amount j using first i-1 type of coins.
                    dp[i][j] = dp[i-1][j]
        # step3: return target from our memorization table
        return dp[n][amount]
    
    def change(self, amount: int, coins: List[int]) -> int:
        """
        Optimized version from space complexity.
        
        dp[j]: number of combinations to construct amount j.
        
        T: O(n*amount)
        S: O(amount)
        """
        # step1
        n = len(coins)
        dp = [0 for _ in range(amount + 1)]
        dp[0] = 1
        
        # step2: recursive formulation
        for i in range(1, n + 1):
            for j in range(amount+1):
                if j - coins[i-1] >= 0:
                    dp[j] = dp[j] + dp[j - coins[i-1]]
        # step3
        return dp[amount]
    
    def change(self, amount: int, coins: List[int]) -> int:
        """
        DP
        T: O(n*amount)
        S: O(n* amount) because we store n* amount sol to subproblems into dp table
        """
        if amount == 0:
            return 1 # there's one way: we don't take any coin to get given amount 0.
        
        n = len(coins)
        if n == 0:
            return 0 # shit question this should not have this test case fff
        
        dp = [[0 for _ in range(amount+1)] for _ in range(n)]
        
        for i in range(n):
            # base case
            dp[i][0] = 1
            for j in range(1, amount+1):
                if j-coins[i] >= 0:
                    if i == 0:
                        dp[i][j] = dp[i][j-coins[i]]
                    else:
                        dp[i][j] = dp[i-1][j]+dp[i][j-coins[i]]
                else:
                    if i==0:
                        dp[i][j] = 0 # impossible to make it
                    else:
                        dp[i][j] = dp[i-1][j]
        
        return dp[n-1][amount]
    
    def change(self, amount: int, coins: List[int]) -> int:
        """
        Brute Force: TLE
            5
            /1
           4
           /1       \ 2
          3           2
         /1    \ 2   /1  \2
        2       1   1     0
        /1 \ 2  /   /1
       1    0  0   0
      / 1
     0
        2+2+1 and 2+1+2 are consider one to our answer. So, we need to get unique combination but at the same time each coin could be choost unlimited times.
        
        Note: 
            Compare to LC 78 subsets, given a array without duplicates, to generate all unique combinations. 
            Because in this question each element could be used once, we can simply to do it by s=i+1(for next level of recursion tree). 
            But, here there is no this limit. So we need sort our current combination to get unique all combinations.
        """
        n = len(coins)

        if amount == 0:
            return 1 # there's one way: we don't take any coin to get given amount 0.
        if n == 0:
            return 0 # shit question this should not have this test case fff        
        
        def backtrack(s, t, cur = []):
            if t == 0:
                # to get unique combination
                if sorted(cur.copy()) not in ans:
                    ans.append(sorted(cur.copy()))
                return 
            
            for i in range(n):
                if t-coins[i] < 0:
                    continue
                cur.append(coins[i])
                backtrack(i, t-coins[i], cur)
                cur.pop()
        ans = []
        backtrack(0, amount, [])
        return len(ans)