Solutions

# DP top down or bottom up. Check all cases: skip, pick.
# dp

# Top-down DP - O(n * m) time, O(n * m) space [m is the given amount]
# w/o memoization: O(2^(max(n,m))) time, O(max(n,m)) space
def change1(amount: int, coins: list[int]) -> int:
    #coins.sort() # not really needed
    dp = {}
    # or array:
    # dp = [[-1] * (amount+1) for _ in range(len(coins) + 1)]
    
    def dfs(curr: int, i: int) -> int:
        if curr > amount or i >= len(coins):
            return 0
        if curr == amount:
            return 1
        if (curr, i) in dp:
            return dp[(curr, i)]

        res = dfs(curr, i+1)            # skip
        res += dfs(curr + coins[i], i)  # pick - NB stay at index i to allow for multiple pick of the same number
        dp[(curr, i)] = res
        return dp[(curr, i)]

    return dfs(0, 0)

        
# Bottom-up DP - O(n*m) time, O(n*m) space
def change(amount: int, coins: list[int]) -> int:
    coins.sort() # not really needed, but makes it easier to understand the logic of the loops. If removed, the if in the loop would move one line below
    n = len(coins)
    dp = [ [0] * (amount+1) for _ in range(n + 1)]
    # dp[i][a] = number of ways to reach amount a using coins from index i onward

    # Base case: only 1 way of making 0 amount
    for i in range(n+1):
        dp[i][0] = 1

    # NB: coins in outer loop to count combinations
    # if coins were in inner loop, we'd count permutations (in which order matters)
    for i in range(n-1, -1, -1):
        for a in range(amount+1):
            if a >= coins[i]: # if we can use current coin
                dp[i][a] = dp[i+1][a]           # skip
                dp[i][a] += dp[i][a - coins[i]] # pick
    
    return dp[0][amount]