Coin change problem¶

Understanding basic recursion¶

In [1]:

def solve(amount, coin):
    """
    # created this to understand what will happen
    # when we have a particular coin and a given amount
    """
    # print("amount: ", amount)
    # base case
    if amount < coin:
        return 0

    acc = 1 + solve(amount - coin, coin)
    return acc

def solve(amount, coin): """ # created this to understand what will happen # when we have a particular coin and a given amount """ # print("amount: ", amount) # base case if amount < coin: return 0 acc = 1 + solve(amount - coin, coin) return acc

In [2]:

solve(7, 1)

solve(7, 1)

Out[2]:

7

Working solution with some problems¶

The explanation below is perfect but the code maybe slightly incorrect although it works perfectly on all the test cases.

In [3]:

def solve_rec(amount, coins):

    """
    Logic: Out of all possible combinations of the coins(which
    is what can be seen by the recursion tree), we have to find that
    1 combination that makes up to the given amount using minimum number of coins.
    We are creating the variable `minimum` which is initialized with
    max value, now it is getting updated everytime during the recursion
    when it's previous value is more than the current
    """

    # base case
    if amount == 0:
        return 0

    # this case comes up in the recursion
    # tree path when the amount becomes -ve
    # suppose the amount is 7 and you are
    # reducing it by coin value 5, when you
    # use the first coin, you are left with amount=2
    # and when you try to use the coin again
    # you will be getting -3 which is incorrect
    # hence for that "path" in the recursion
    # tree will not be a valid one and hence we return inf.
    if amount < 0:
        return float("inf")

    minimum = float("inf")
    ans = float("inf")

    # since we have coins of multiple denomination
    # we will use them one by one and calculate
    # all the possible outcomes via recursion
    for coin in coins:
        # recursive relation
        # here is where we build the recursion tree
        # INTEGER OVERFLOW MAY OCCUR HERE
        ans = 1 + solve_rec(amount - coin, coins)
        if ans != float("inf"):
            minimum = min(minimum, ans)

    return minimum

def solve_rec(amount, coins): """ Logic: Out of all possible combinations of the coins(which is what can be seen by the recursion tree), we have to find that 1 combination that makes up to the given amount using minimum number of coins. We are creating the variable `minimum` which is initialized with max value, now it is getting updated everytime during the recursion when it's previous value is more than the current """ # base case if amount == 0: return 0 # this case comes up in the recursion # tree path when the amount becomes -ve # suppose the amount is 7 and you are # reducing it by coin value 5, when you # use the first coin, you are left with amount=2 # and when you try to use the coin again # you will be getting -3 which is incorrect # hence for that "path" in the recursion # tree will not be a valid one and hence we return inf. if amount < 0: return float("inf") minimum = float("inf") ans = float("inf") # since we have coins of multiple denomination # we will use them one by one and calculate # all the possible outcomes via recursion for coin in coins: # recursive relation # here is where we build the recursion tree # INTEGER OVERFLOW MAY OCCUR HERE ans = 1 + solve_rec(amount - coin, coins) if ans != float("inf"): minimum = min(minimum, ans) return minimum

In [4]:

def minimum_coins(coins, amount):

    ans = solve_rec(amount, coins)
    if ans == float("inf"):
        return -1
    else:
        return ans

def minimum_coins(coins, amount): ans = solve_rec(amount, coins) if ans == float("inf"): return -1 else: return ans

In [5]:

coins = [1, 2, 5]
amount = 11

# coins = [2]
# amount = 3

# coins = [1]
# amount = 0

coins = [1, 2, 5] amount = 11 # coins = [2] # amount = 3 # coins = [1] # amount = 0

In [6]:

minimum_coins(coins, amount)

minimum_coins(coins, amount)

Out[6]:

3

Coin change - slightly better solution¶

In [7]:

def coin_change(coins, amount):
    def solve(amount):
        if amount == 0:
            return 0

        if amount < 0:
            return float("inf")

        minimum = float("inf")
        for coin in coins:
            ans = solve(amount - coin)
            if ans != float("inf"):

                # what's better?
                # well, we should add 1 to the ans
                # when it is not infinity
                # meaning when it is valid
                minimum = min(1 + ans, minimum)

        return minimum

    ans = solve(amount)

    return ans

def coin_change(coins, amount): def solve(amount): if amount == 0: return 0 if amount < 0: return float("inf") minimum = float("inf") for coin in coins: ans = solve(amount - coin) if ans != float("inf"): # what's better? # well, we should add 1 to the ans # when it is not infinity # meaning when it is valid minimum = min(1 + ans, minimum) return minimum ans = solve(amount) return ans

In [8]:

coins = [1, 2, 5]
amount = 11

coin_change(coins, amount)

coins = [1, 2, 5] amount = 11 coin_change(coins, amount)

Out[8]:

3

Recursion + Memoization¶

In [9]:

def solve_memo(amount, coins, dp):

    if amount == 0:
        return 0

    if amount < 0:
        return float("inf")

    ans = float("inf")
    minimum = float("inf")

    if dp[amount] != -1:
        return dp[amount]

    for coin in coins:
        # recursive relation
        # here is where we build the recursion tree
        ans = 1 + solve_memo(amount - coin, coins, dp)
        if ans != float("inf"):
            minimum = min(minimum, ans)

    dp[amount] = minimum

    return dp[amount]

def solve_memo(amount, coins, dp): if amount == 0: return 0 if amount < 0: return float("inf") ans = float("inf") minimum = float("inf") if dp[amount] != -1: return dp[amount] for coin in coins: # recursive relation # here is where we build the recursion tree ans = 1 + solve_memo(amount - coin, coins, dp) if ans != float("inf"): minimum = min(minimum, ans) dp[amount] = minimum return dp[amount]

In [10]:

def minimum_coins_memo(coins, amount):

    dp = [-1] * (amount + 1)

    ans = solve_memo(amount, coins, dp)
    if ans == float("inf"):
        return -1
    else:
        return ans

def minimum_coins_memo(coins, amount): dp = [-1] * (amount + 1) ans = solve_memo(amount, coins, dp) if ans == float("inf"): return -1 else: return ans

In [11]:

coins = [1, 2, 5]
amount = 100

# coins = [2]
# amount = 3

# coins = [1]
# amount = 0

coins = [1, 2, 5] amount = 100 # coins = [2] # amount = 3 # coins = [1] # amount = 0

In [12]:

minimum_coins_memo(coins, amount)

minimum_coins_memo(coins, amount)

Out[12]:

20

Tabulation¶

In [13]:

def solve_tabulation(coins, amount):

    dp = [float("inf")] * (amount + 1)

    dp[0] = 0

    # in this case we have to build from bottom to go up
    # trying to solve for every amount figure from 1 to n
    for i in range(1, amount + 1):
        for coin in coins:
            # check for valid index and also check
            # if i-coin is not infinite otherwise there
            # will be integer overflow
            if i - coin >= 0 and dp[i - coin] != float("inf"):
                dp[i] = min(dp[i], 1 + dp[i - coin])

    if dp[amount] == float("inf"):
        return -1

    return dp[amount]

def solve_tabulation(coins, amount): dp = [float("inf")] * (amount + 1) dp[0] = 0 # in this case we have to build from bottom to go up # trying to solve for every amount figure from 1 to n for i in range(1, amount + 1): for coin in coins: # check for valid index and also check # if i-coin is not infinite otherwise there # will be integer overflow if i - coin >= 0 and dp[i - coin] != float("inf"): dp[i] = min(dp[i], 1 + dp[i - coin]) if dp[amount] == float("inf"): return -1 return dp[amount]

In [14]:

def minimum_coins_tabulation(coins, amount):
    ans = solve_tabulation(coins, amount)
    return ans

def minimum_coins_tabulation(coins, amount): ans = solve_tabulation(coins, amount) return ans

In [15]:

coins = [1, 2, 5]
amount = 100

# coins = [2]
# amount = 3

# coins = [1]
# amount = 0

coins = [1, 2, 5] amount = 100 # coins = [2] # amount = 3 # coins = [1] # amount = 0

In [16]:

minimum_coins_tabulation(coins, amount)

minimum_coins_tabulation(coins, amount)

Out[16]:

20