coin_dp.py

def coin_outer_amount_inner(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]


def amount_outer_coin_inner(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] += dp[i - coin]
    return dp[amount]


def coin_outer_amount_inner_sequences(coins, amount):
    dp = [[] for _ in range(amount + 1)]
    dp[0] = [[]]

    for coin in coins:
        for i in range(coin, amount + 1):
            for seq in dp[i - coin]:
                dp[i].append(seq + [coin])

    return dp[amount]


def amount_outer_coin_inner_sequences(coins, amount):
    dp = [[] for _ in range(amount + 1)]
    dp[0] = [[]]

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                for seq in dp[i - coin]:
                    dp[i].append(seq + [coin])

    return dp[amount]


def coin_outer_amount_inner_sequences_desc(coins, target):
    coins = sorted(coins, reverse=True)
    return coin_outer_amount_inner_sequences(coins, target)


def amount_outer_coin_inner_sequences_desc(coins, target):
    coins = sorted(coins, reverse=True)
    return amount_outer_coin_inner_sequences(coins, target)


print(coin_outer_amount_inner([1, 2], 4))                # Output: 3
print(amount_outer_coin_inner([1, 2], 4))                # Output: 5
print(coin_outer_amount_inner_sequences([1, 2], 4))      # Output: [[1, 1, 1, 1], [1, 1, 2], [2, 2]]
print(amount_outer_coin_inner_sequences([1, 2], 4))      # Output: [[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2]]
print(coin_outer_amount_inner_sequences_desc([1, 2], 4)) # Output: [[2, 2], [2, 1, 1], [1, 1, 1, 1]]
print(amount_outer_coin_inner_sequences_desc([1, 2], 4)) # Output: [[2, 2], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 1, 1]]