518. Coin Change 2

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        """tc O(KN) sc O(KN)
        main idea: Top Down  
        dp[i][j]: ways of COMBINATION to fill j amount with first time using coins[i-1]
        """
        n  = len(coins)
        dp = [[0 for x in range(amount+1)] for _ in range(n+1)]
        # base case 
        dp[0][0] = 1
        for i in range(1,n+1):
            dp[i][0] = 1
        for i in range(1,len(coins)+1):
            for j in range(1,amount+1):
                if j >= coins[i-1]:
                    # here use dp[i][j-coins[i-1]] instead of dp[i-1][j-coins[i-1]] 
                    # because it includes repeatedly using coin[i-1]
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][amount]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        """ tc O(Amount*len(coins)) sc O(amount)s
        main idea: Top Down  
        dp[i][j]: ways of COMBINATION to fill j amount with first time using coins[i-1]
        """
        n  = len(coins)
        dp = [0 for x in range(amount+1)] 
        dp[0] =1 
        for i in range(1,n+1):
            for j in range(1,amount+1):
                dp[j] = dp[j] + (dp[j-coins[i-1]] if j >= coins[i-1] else 0)
        return dp[amount]