You are given an array of coins and an interger k. Return min number of coins to make value k.
Given an array of integers as coins and a number k. Return minimum number of coins that can be used to make k. You may consider that coins will always have 1 cent in there so that there will be no such case that the combination is not possible.
-
We will receive and array of coins and an integer sum
-
We will initialize a memo table of length sum+1. That is because in the end we will have result in memo[sum]
-
Initialize memo array with Integer.MAX_VALUE. Since we are interested in min number of coins we are initializing with max value of integer.
-
We will be using bottom up approach that means we will first calculate min number of ways to make 1 coin, followed by 2 coins, 3 coins etc until we reach sum.
-
In this case we know that to achieve 0 sum we need 0 coins. This memo[0] = 0.
-
Then we will start a loop from 1 to sum+1. Followed this loop we need to take one coin from the array of coins and subtract from i until we reach 0.
-
Thus we will have a nested loop starting from 0 to end of coins array.
-
In this loop we are going to check if the coin value is less than or equal to i value then we will take the previously calculated value from memo table
int sub_res = memo[i - coins[j]]; -
Lastly we will do this
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < memo[i])
memo[i] = sub_res + 1;