Скачать с ютуб Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode) в хорошем качестве

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