题解 | #兑换零钱#
兑换零钱
https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72?tpId=230&tqId=2383902&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
# from subprocess import _InputString
import sys
# for line in sys.stdin:
# a = line.split()
# print(int(a[0]) + int(a[1]))
n,amount = map(int,input().split())
arr = list(map(int,input().split()))
dp = [float("inf") for i in range(amount+1)]
dp[0] = 0
#dp数组是滚动更新的，每经过一次遍历arr的元素，dp数组更新一次，从arr开始更新到amount
for i in range(len(arr)):
for j in range(arr[i],amount+1):
dp[j] = min(dp[j],dp[j-arr[i]]+1)
print(dp[amount] if dp[amount]!=float("inf") else -1)
查看23道真题和解析
联想公司福利 1500人发布