Why is its optimal approach different than coin change problem for min no of coins?


#1

the coin change uses Dp whereas this one uses greedy. Wont it give wrong outputs ?


#2

This is because, in coin change problem, number of coins is very less. In this question number of coins are very large. So you can’t solve it with bottom up or top down dp approach.
In this question, greedy works because of sequential property of series.


#3

Taken from the wiki on zeckendorf’s theorem

Suppose you decomposed 64 into its fibonnaci addends: 64 = 55 + 8 + 1.
Any other decomposition would further subdivide the existing addends (55,8), thus giving you a larger set. Therefore, on some level this is the minimum set that you could obtain, and it is through the greedy method.


#4

Isn’t this because 1 is always waiting for you at the end so no matter what you can always work the greedy approach while in coin change problem you would not be able to get an ans for example you have coins of denomination 2 3 and you have to make a sum of 10 , now if you apply greedy approach you are stuck after subtracting 3 times 3 from 10 as you will have 1 left for which you dont have any coin for , while here 1 1 2 3 5 … so no matter what 1 is there … hope it helped , if I am wrong please let me know


#5

let’s take an example you have 1 , 5 , 8 coins you want to make 10 following the greedy approach you get 8+1+1 i.e 3 coins however the ans is 5+5 , 2 coins @aviral2318_6ebd020fd seems to be correct because we have the availability of basic coins like 1,2,3,5 so the approach depends on the coins available .