<filename>Problems/Dynamic Programming/Medium/CoinChange2/coin_change2.py
from functools import lru_cache
from typing import List


# Top-down (Memoization)
# TC: O(N * M); SC: O(N * M)
def change(self, amount: int, coins: List[int]) -> int:
    @lru_cache(None)
    def dp(amt: int, n: int) -> int:
        if amt == 0:
            return 1

        if n < 0 or amt < 0:
            return 0

        return dp(amt - coins[n], n) + dp(amt, n - 1)

    return dp(amount, len(coins) - 1)

# Bottom-up (Tabulation)
# TC: O(N * M); SC: O(N * M)
def change(self, amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        dp[i][0] = 1
        for j in range(1, amount + 1):
            dp[i][j] = dp[i - 1][j]
            if j - coins[i - 1] >= 0:
                dp[i][j] += dp[i][j - coins[i - 1]]
    return dp[n][amount]

# Bottom-up (Tabulation)
# TC: O(N * M); SC: O(N)
def change(self, amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [0 for _ in range(amount + 1)]
    dp[0] = 1
    for i in range(n):
        for j in range(1, amount + 1):
            if j - coins[i] >= 0:
                dp[j] += dp[j - coins[i]]

    return dp[amount]
<filename>Problems/Dynamic Programming/Medium/CoinChange2/coin_change2.py
from functools import lru_cache
from typing import List


# Top-down (Memoization)
# TC: O(N * M); SC: O(N * M)
def change(self, amount: int, coins: List[int]) -> int:
    @lru_cache(None)
    def dp(amt: int, n: int) -> int:
        if amt == 0:
            return 1

        if n < 0 or amt < 0:
            return 0

        return dp(amt - coins[n], n) + dp(amt, n - 1)

    return dp(amount, len(coins) - 1)

# Bottom-up (Tabulation)
# TC: O(N * M); SC: O(N * M)
def change(self, amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        dp[i][0] = 1
        for j in range(1, amount + 1):
            dp[i][j] = dp[i - 1][j]
            if j - coins[i - 1] >= 0:
                dp[i][j] += dp[i][j - coins[i - 1]]
    return dp[n][amount]

# Bottom-up (Tabulation)
# TC: O(N * M); SC: O(N)
def change(self, amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [0 for _ in range(amount + 1)]
    dp[0] = 1
    for i in range(n):
        for j in range(1, amount + 1):
            if j - coins[i] >= 0:
                dp[j] += dp[j - coins[i]]

    return dp[amount]
# Top-down (Memoization) # TC: O(N * M); SC: O(N * M) # Bottom-up (Tabulation) # TC: O(N * M); SC: O(N * M) # Bottom-up (Tabulation) # TC: O(N * M); SC: O(N)