You are not logged in. Please login at www.codechef.com to post your questions!

×

Coin change problem

How to solve coin change problem if we have limited number of coins?

asked 31 Aug '18, 22:29

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%


You can keep a map consisting of the count of each coin value. Each time you use a coin, decrement it's count in the map. If while adding a coin if you see that the count of the coin value is <= 0, then don't add the coin. I guess this might solve the problem.

link

answered 31 Aug '18, 23:23

horsbug98's gravatar image

4★horsbug98
3236
accept rate: 21%

it would again make the complexity go back to O(2^n) how would we do dp on this problem assuming we have only one of a kind coin?

(03 Sep '18, 20:45) phantomhive4★

You can make a array of total coins given. For e.g., let's assume there are 4 coins given {1,2,3,4} and each of 2 units then make a array of {1,1,2,2,3,3,4,4} and then proceed for normal approach of DP how many times you can make up to 'N'.

link

answered 16 Sep '18, 21:08

rs07's gravatar image

4★rs07
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,091

question asked: 31 Aug '18, 22:29

question was seen: 168 times

last updated: 31 Aug '18, 22:29