题解 | 兑换零钱(一)

零钱兑换问题是一个经典的动态规划应用，目标是在给定硬币面额数组arr和目标金额aim的情况下，计算出最少需要多少枚硬币才能凑成该金额，如果无法凑出则返回 -1。

实现步骤

1. 定义状态 设 dp[i] 表示凑成金额 i 所需的最少硬币数。初始时 dp[0] = 0（金额为0不需要硬币），其他位置初始化为正无穷大float('inf')，表示暂不可达。
2. 状态转移方程 对于每个硬币x ，遍历所有金额 i（从 x到aim），更新：
3. dp[i] = min(dp[i], dp[i - x] + 1)复制其中 dp[i - x] + 1 表示用一个当前硬币加上凑成剩余金额的最优解。
4. 返回结果 若 dp[aim] 仍为无穷大，返回 -1；否则返回其值。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        dp = [float('inf')]*(aim+1)
        dp[0] = 0
        for x in arr:
            for i in range(x,aim+1):
                dp[i] = min(dp[i],dp[i-x]+1)
        return dp[-1] if dp[-1]!=float('inf') else -1