Coin change problem
Në shqip: Problemi i kusurit
ShpjegimiSQ
Me sa më pak monedha si e formon një shumë? Me monedhat e euros, „merr më të madhen“ (greedy) funksionon, por për monedha të çuditshme duhet programim dinamik. Shembull i mirë i dallimit mes tyre.
EnglishEN
How do you make an amount with as few coins as possible? With euro coins, “take the biggest” (greedy) works, but for unusual coins you need dynamic programming. A good example of the difference.
Si ta mendosh
Si arkëtari që kthen kusurin me sa më pak monedha.
Lexoje në anglisht
Like a cashier giving change with as few coins as possible.
Shembull kodipython
def monedhat(shuma, m):
dp = [0] + [float("inf")] * shuma
for s in range(1, shuma + 1):
dp[s] = min((dp[s - c] + 1 for c in m if c <= s), default=dp[s])
return dp[shuma]