liao24hoho
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
the above code assumes the denoms are 2,3 and 5.
- liao24hoho June 01, 2012Comment hidden because of low score. Click to expand.
1
of 1 vote
logic is here:it is O(S) and I doubt it is the same algorithm with the above code
create an array of S elements,call it set,which stores the minimum number of coins,
1.set[0],set[1] unused,set[2]=1,set[3]=1,set[4]=2,set[5]=1,
2.start from k=6,we check
set[k-2],set[k-3],set[k-5],pick the minimum of these three and add it by one and take it as the value of set[k],keep going until we reach S.
pretty easy DP question.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I wonder "eliminate duplicate" means " eliminate all the other cases of duplicates but retain one" or "eliminate all the cases of a duplicated number",
- liao24hoho June 01, 2012if it is the former one,one pass is feasible.