Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://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. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.
Examples:
1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
2
Input: amount = 3, coins = [2]
Output: 0
Can't make change for this amount given the coins we have.
This problem is very similar to the 0 / 1 knapsack problem.
We will use a bottom up dynamic programming approach to build to our final answer.
We will consider the total ways to make change with just the 1st coin, with just the 1st and 2nd coin, with just the 1st, 2nd, and 3rd, coin, and so on...
Complexities
A is the amount to make change for.
n is the total denominations avaliable to us.
Time: O( A * n )
For each denomination we will be solving A subproblems. So for each of the n we will be doing A work, hence multiplication.
Space: O( A * n )
Hold the answer to all subproblems.
Note: We can do this in just O( A ) space but we did it this way for simplicity
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Watch video Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode) online without registration, duration hours minute second in high quality. This video was added by user Back To Back SWE 20 January 2019, don't forget to share it with your friends and acquaintances, it has been viewed on our site 167,867 once and liked it 5.3 thousand people.