题解 | #找零# 动态规划
找零
http://www.nowcoder.com/questionTerminal/944e5ca0ea88471fbfa73061ebe95728
动态规划求解
cost = int(input())
money = 1024 - cost
def func(money):
dp = [money for _ in range(money + 1)]
dp[0] = 0
amount = [1, 4, 16, 64]
for i in range(1,money+1):
for j in range(len(amount)):
if i >= amount[j]:
dp[i] = min(dp[i], dp[i - amount[j]] + 1)
return dp[money]
print(func(money))
