Bissoy.com
Doctors Medicines MCQs Q&A

Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem? Correct Answer O(S)

To get the optimal solution for a sum S, the optimal solution is found for each sum less than equal to S and each solution is stored. So, the space complexity is O(S).

Related Questions

You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
A has 50 coins of 10 paise denominations. While B has 10 coins of 50 paise denominations. C has 20 coins of 25 paise denominations while D has 25 coins of 20 paise denominations. The average number of paise per person is :
You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
A bill for ₹1,840 is paid in the denominations of ₹50, ₹20 and ₹10 notes. 50 notes in all are used. Consider the following statements : 1. 25 notes of ₹50 are used and the remaining are in the denominations of ₹20 and ₹10. 2. 35 notes of ₹20 are used and the remaining are in the denominations of ₹50 and ₹10. 3. 20 notes of ₹10 are used and the remaining are in the denominations of ₹50 and ₹20. Which of the above statements are not correct? 
Anika and Anushree always used to spend their time by playing coin games after their school hours. Once they decided to play a game of coins in which one player has to guess the number of coins by closing her eyes with the help of clues given by other player. During Anika’s turn, she closed Anushree’s eyes and put some coins on table. She then gave her clue by saying that one fourth of coins are showing their heads but if I turn over two coins then in that case, one third of them will show heads. So, Anushree can you guess how many number of coins I initially placed on the table?
A, B and C has few coins. Eight times the number of coins that A has equals to five times the number of coins B has, while seven times the number of coins B has is equal to eleven times the number of coins C has. Find the minimum number of coins with A, B and C put together.
In a rare coin collection, all coins are either pure gold or pure silver , and there is initially one gold coin for every three silver coins . With the addition of 10 more gold coins to the collection, the ratio of gold coins to silver coins is 1 to 2. Based on this information , how many total coins are there now in this collection (after the acquisition)?
The question below is followed by two statements I and II. You have to determine whether the data given is sufficient for answering the question. You should use the data and your knowledge of mathematics to choose the best possible answer.  Belly has some coins out of which some are of 25 Cent and Some are of 50 Cent. If he has a total of 250 coins, how many coins does he have of 25 Cent? I) Belly has three times as many as 50 Cent coins as 25 Cent coins. II) Belly has 20 more 25 cent coins than the 50 Cent coin.
Divya has 1500 coins which are in the combination of gold and silver in the ratio of 5 ∶ 7. She distributed the silver coins among his three sons Nimesh, Monil and Gaurav in the ratio of 7 ∶ 12 ∶ 6. If Gaurav and Monil combined 60% of their silver coins and made jewelry from it and sell the remaining silver coins at Rs. 500 per coin, then the amount earned from selling of silver coin was distributed between Monil and Gaurav in the ratio of 12 ∶ 13. Find the difference between the amount earned by Gaurav and Monil from the silver coin transaction.
A wallet has three denominations of coins – Rs. 1, Rs. 5 and Rs. 10 in the ratio of 2 ∶ 3 ∶ 5. A coin is drawn at random. What us the probability that coin drawn is not a Rs. 5 coin of wallet has a total of 30 coins?