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

Опубликовано: 02 Октябрь 2024
на канале: Back To Back SWE

167,867

5.3k

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