[[Dynamic Programming Primer]]

Problem

The “Unbounded Knapsack” Pattern.

You are given an array of coin denominations (e.g., [1, 2, 5]) and a total amount of money (e.g., 11). Find the fewest number of coins that you need to make up that amount. You can use each coin type as many times as you want. If it’s impossible, return -1. its an unbounded knapsack problem because there is no contraint on how many times we can reuse the same coins for eg to make target 3 we can use 1 3 times ( 3 coins) use a 1 and a 2 hence (2 coins) the answer is 2 since thats the least number of coins we need

Brainstorming

In this example we want to minimize the number of coins to reach an amount. if we use the Tabulation approach then maybe we can build up our solution to the amount value. so essentially we want dp[amount] and we will calculate how many minimum number of coins we need to build say amount = 1 or 2 or 3 all the way to dp[amount] to do this we would first need to define a base case. How many coins do we need to make amount 0? in my opinion to make nothing you need nothing so in tabulation form dp[0] = 0 the next obvious question then is how many coins do we need to make amount 1 well its clear 1 since all the other coins are bigger than the amount dp[1] = 1

Now that we have gotten our base cases ready lets see how big our state array dp needs to be since we want to hold answer for dp[amount] it makes sense to make the dp array amount + 1

But now what should be the recurrence equation? we have defined number of coins that we want to use [1,2,5] following the logic of “at the last step” we can just check for amount = 11

if our last coin was 1 then our recurrence eq is 1 + dp[amount -1] i.e 1 + dp[10]
 if our last coin was 2 then our reccurence eq is 1 + dp[amount -2] i.e 1 + dp[9]
 if our last coin was 5 then our reccurence eq is 1 + dp[amount -5] i.e 1 + dp[5]

in all the above cases we add 1 so that the current last coin [1 or 2 or 5] also gets counted

now we want the minimum of the above 3 min(1 + dp[10], 1+ dp[9], 1 + dp[6]

we now need to equate it out.

The first idea that comes to my mind is we keep a current_coin_count and compare it with 1 + dp[amt - coin] a minimum of both goes in the current_coin_count that then gets assigned to dp[amt]

we would also need to handle a edge case “what if a subproblem is impossible?” l lets take an hypothetical example where the coins are [2,5] and we want to make dp[3] then its impossible so in that case we want to make sure that we write “impossible” to its output but how to do it in code?  We can’t use 0, because that’s a valid answer. We could use -1, but a common trick is to use infinity. The minimum of anything and infinity is always the other thing, which makes the math clean.

lets try to write the algorithm

1. initialise a dp = [float("inf")] * amount+1
2. set base case dp[0] = 0
3. now we will loop a for loop for amt in amount + 1
   1. for each partial amt we will check for each coin for coin in coins
      1. now for each coin we will check if they “fit” the amount or not if amt >= coin
         1. its a potential coin !! potential_coin = 1 + dp[amt - coin]
      2. now the curcial part is our potential coin making the count smaller or not
         1. dp[amt] = min(potenial_coin, dp[amt]) # comparing it against prev coins

amount = 11

coins = [1,2,5]

def coin_change(amount):
	dp = [float('inf')] * amount + 1
	for amt in range(1, amount+1):
		for coin in coins:
			if amt >= coin:
				potential_coins = 1 + dp[amt - coin]
				dp[amt] = min(dp[amt], potenital_coints)

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

lets see this with an example 5

1. we start with amt 1
   1. for coin in coins
      1. coin 1 ( 2 and 5 are skipped)
         1. potential_coin = 1 + dp[1-1] i.e dp[0] which is 0 hence potential coin is 1
         2. dp[1] = min(dp[1], 1) since they are both 1 hence dp[1] is 1
2. we go to amt 2
   1. for coin in coins
      1. coin 1 (coin 5 skipped)
         1. potential_coins = 1 + dp[2-1] ie dp[1] which is 1 hence the potential coin is 2
         2. dp[2] = min(dp[2], 2) since we don’t have dp[2] yet we are comparing infinity to 2 hence min is 2 which will get assigned to dp[2]
      2. coin 2
         1. potential_coins = 1 + dp[2-2] ie dp[0] which is 0 hence potential_coins is 1
         2. dp[2] = min(dp[2], 1) since dp[2] is 2 we will take 1 and assign it to dp[2] = 2
3. we go to amt 3
   1. for coin in coins
      1. coin 1 (coin 5 is skipped)
         1. potential_coins = 1 + dp[3-1] ie dp[2] which is 1 hence the potential_coins is 2
         2. dp[3] = min(dp[3], 2) since we don’t have dp[3] yet we are comparing infinity to 2 hence for dp[3] we are going to assign 2
      2. coin 2
         1. potential_coins = 1 + dp[3-2] i.e dp[1] which is 1 hence the potential coins is 2
         2. dp[3] = min(dp[3], 2) since they both are 2 hence the final value for dp[3] is 2
4. we go to amt 4
   1. for coin in coins
      1. coin 1 ( coin 5 is skipped)
         1. potential_coins = 1 + dp[4-1] ie dp[3] which is 2 hence the potential_coins is 3
         2. dp[4] = min(dp[4], 3) since we don’t have dp[4] yet we are comparing infinity with 3 hence 3 gets assigned to dp[4]
      2. coin 2
         1. potential_coins = 1 + dp[4-2] ie dp[2] which is 2 hence the potential coins is 3
         2. dp[4] = min(dp[4], 3) since they both are 3 hence the final value for dp[4] is 3
5. we go to amt 5
   1. for coin in coins
      1. coin 1
         1. potential_coins = 1 + dp[5-1] ie dp[4] which is 3 hence potential_coins is 3
         2. dp[5] = min(dp[5] , dp[4]) since we don’t have dp[5] yet we are comparing infinity with 3 hence 3 gets assigned to dp[5]
      2. coin 2
         1. potential_coins = 1 + dp[5-2] ie dp[3] which is 2 hence the potential_coins is 2
         2. dp[5] = min(dp[5], 2) since 2 is smaller than 3 the new value for dp[5] is 2
      3. coin 5
         1. potential_coins = 1 + dp[5-5] ie dp[0] which is 0 hence the potential coins is 1
         2. dp[5] = min(dp[5], 1) so the current value is 2 and the new potential value is 1 , obviously since 1 is small that gets assigned to dp[5]

hence for dp[5] the answer is 1 is the minimum number of coins we need to make this amount