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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching

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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

Видео Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode) канала Back To Back SWE