23.07.29 Today’s Leetcode

518. Coin Change II (medium)

DFS

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)

        @functools.lru_cache(None)
        def dfs(amount, index):
            if amount == 0:
                return 1
            if amount < 0:
                return 0
            temp = 0
            for i in range(index, n):
                coin = coins[i]
                temp += dfs(amount - coin, i)
            
            return temp
        
        return dfs(amount, 0)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)

        # Tabulation ..!!!!

        dp = [[0 for i in range(amount+1)] for j in range(n+1)]

        for i in range(amount+1):
            if i % coins[0] == 0:
                dp[0][i] = 1

        for ind in range( 1 , n ):
            for cur_amount in range(amount + 1):
    
                not_take = dp[ind - 1][cur_amount]

                take = 0
                if cur_amount >= coins[ind]:
                    take = dp[ind][cur_amount - coins[ind]]
                
                dp[ind][cur_amount] = take + not_take
        
        return dp[n-1][amount]


        # Memoization ..!!!

        # for problems where we can take same element multiple times 
        # base condition is .... 
        # if index == 0: return ( target // values[0]) * price[0]  (or) (target % val[0])*pri[0]

        """
        dp = [[-1 for i in range(amount+1)] for j in range(n+1)]
        def solve( ind , cur_amount ):
            
            # if cur_amount == 0: return 1
            # if ind == -1: return 0 
            
            if ind == 0:                                # !!!!!!!
                if (cur_amount % coins[0]) == 0: 
                    # then there is posibility
                    return 1
                return 0

            if dp[ind][cur_amount] != -1: return dp[ind][cur_amount]

            not_take = solve(ind-1 , cur_amount)

            take = 0
            if cur_amount >= coins[ind]:
                take = solve( ind , cur_amount - coins[ind] )
            
            dp[ind][cur_amount] = take + not_take
            return dp[ind][cur_amount]

        return solve( n-1 , amount )
        """