# Coin change problem¶

##### Understanding basic recursion¶

In [1]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
minimum_coins(coins, amount)
```

minimum_coins(coins, amount)

Out[6]:

3

##### Coin change - slightly better solution¶

In [7]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
minimum_coins_memo(coins, amount)
```

minimum_coins_memo(coins, amount)

Out[12]:

20

##### Tabulation¶

In [13]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
minimum_coins_tabulation(coins, amount)
```

minimum_coins_tabulation(coins, amount)

Out[16]:

20