题解 | #找零# 动态规划

动态规划求解

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))