23.08.11 Today’s Leetcode

518. Coin Change II (medium)

weird DP, my solution

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = defaultdict(list)
        dp[0] = [0] * n
        dp[0][0] = 1
        
        for cur in range(1, amount + 1):
            temp = [0] * n
            for i in range(n): 
                arr = dp[cur - coins[i]]
                if cur - coins[i] == 0:
                    arr = [0] * n
                    arr[i] = 1
                if not arr:
                    continue
                for j in range(i + 1):
                    temp[i] += arr[j]
            dp[cur] = temp
        
        # print(dp)

        return sum(dp[amount])

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 )
        """