题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
class Solution:
def minMoney(self, arr: List[int], aim: int) -> int:
dp = [float('inf')]*(aim+1)
dp[0] = 0
for coin in arr:
for x in range(coin, aim+1):
dp[x] = min(dp[x], dp[x-coin]+1)
return dp[-1] if dp[-1] != float('inf') else -1
