Total Unique Ways To Make Change - Dynamic Programming ('Coin Change 2' on LeetCode)

📹 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

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents:

Addressing Temporal Circumstances 0:00 - 0:11
The Problem Introduction 0:11 - 1:30
Outlining Our Subproblems 1:30 - 2:50
Defining Our Base Cases 2:50 - 3:45
Establishing Our Subproblem Relationship 3:45 - 4:31
We Are Ready: Filling Out The DP Table 4:31 - 10:28
Time Complexity 10:28 - 10:40
Space Complexity 10:40 - 11:10
Wrap Up 11:10 - 11:23

The code for this problem is in the description. Fully commented for teaching purposes.

[TheinHtikeAung]

"Every single dynamic programming video should start out with the explanation of the subproblem.
This is not about table behind me. It’s about subproblem and how they relate to each other."
Love this!

[xceinie]

I love how you explain this problem and the use of the disclaimer "do not memorize the patter, memorize the subproblem". Your order of explanation, repetition, knowledge of the subject, the thoroughness of your explanation and your enthusiasm are amazing! Thank you for creating this!

[siddharthkhandelwal]

Knowing a concept is one thing, but being able to explain it so well is another .Your explanations are lucid and very easy to understad.

[rahuldeshpande]

Bro, I'm from Toronto. THIS RIGHT HERE IS THE BEST EXPLANATION. Most folks must just go into the table. You did everything. Thank you

[phanichoragudi]

I love the way you merged your video with that of Tushar roy's. 😁

[SV-zios]

Great Explanation! Just loved when you described that a DP problem is not about just showing a dry run.
Just some additions, to be precise the subproblems are -
#ways to get a sum 'n' using S(a, b, c) set of coin = # ways of getting a sum 'n' from S (a, b) (Do not use the c coin) + #ways of getting a sum 'n' from S(a, b, c) with using c at least once (Use the c coin).
This is true as basic set law {X union X complement is equal to universal set} therefore, doesn't matter which coin is choosen as c, therefore it doesn't matter that the order of coins is in ascending order or not.
Now, how to ensure taking at least one coin c => use one coin of c and find #ways of getting a sum of n-c from S(a, b, c) {i.e., for getting sum n-c, it doesn't matter whether coin c was taken or not}

[amitpurohit]

I have recommended all of my friends who wanted to learn dp this shear passion and excitement to teach itself crystal clears all the concepts and doubts...and of course he taught me to think about subproblems...Thank you for this wonderful explanation!!!!

[karthikrangaraju]

For folks who still don't understand the intuition behind "table[row][col - coins[row-1]" and "table[row-1][col]"

Amount 5, with coins [1, 2].
There are 3 ways:

[1+1+1+1+1]
[1+1+1+2]
[2+2+1]


Can be broken down as:


With 2:
Deduct 2 from amount 5, then you have. sub problem which is:
Amount 3, with coins [1, 2]
[1+1+1] = 3. Now just add 2 to it ==> [1+1+1+2] = 5
[2+1] = 3. Now just add 2 to it ==> [2+1+2] = 5

Without 2:
[1+1+1+1+1]

[murtazaroondiwala]

Amazing work! You explain things in a way that even a 6 yrs old child can understand. Keep it up!!

[mei.jourmi]

Really love how concise and informative this video is! Instead of getting straight into coding, thank you for drawing out the table and helping us reason through it in a way that actually makes sense and is succinct!

[tanmaymalhotra]

This is why I love youtube, a person overseas just helped me understand a very crucial technique of dp .. Thank You sir, Keep making such awesome videos!

[ripuvendrasingh]

Bro, my friend asked me to explain this problem even though I knew solution I messed up because explaining DP approach to someone else sucks, but your explanation is brilliant.

[RichardOpokuEngineer]

Where was this guy during my days on campus. Man, I'm impressed. Thank you

[mrkyeokabe]

Thanks for the quality video. You are the most talented algo YouTuber out there!
Note to viewers: If we call this the “unlimited” 0/1 knapsack problem (you can choose unlimited numbers of elements) and the other video Ben refers to as the “basic” 0/1 knapsack problem(you can only choose each element at most once), the only difference between the two seems to be which cells we check with when we fill the table. For both the “basic” and “unlimited” problem, we will check the cell right above the current cell to assess the case when we don’t choose the current element. However, when we choose an element, the “basic” knapsack checks the element that is one row above and element number to the left whereas for the “unlimited” case we just look at the cell in the same row and element number to the left. I think this is a useful perspective to store somewhere in the back of one’s head.

[lifeofbarkin]

I’ve lost it when I saw Tushar 😂 Great work man!

[MrVenona]

I've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.

[daydeveloper]

Honestly what's college without you, my school needs you! Thanks for all the great information and bringing it all together. I am adding "back to back swe" to each of my YouTube searches now lol! Great stuff

[rashmitharavi]

I watched many videos on this problem, This one solved all my doubts. Very greatly explained. Thanks a lot!!!

[CHIRANJIBNANDY]

Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.