Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Examples:
1
Input:: coins = [1, 2, 5], amount = 11
Output 3
2
Input: coins = [2], amount = 3
Output: -1
Approach 1 (Brute Force)
We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.
This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.
Approach 2 (Top Down Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.
Not all paths will yield an answer, some will yield an optimal answer.
Complexities (Top Down)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
Approach 3 (Bottom Up Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.
Complexities (Bottom Up)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will potentially try each of the denominations (there are n of them).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech