题解 | #兑换零钱(一)#

假设有面值为[1, 2,5, 10]的货币。要找23元，找23元的最少货币数作为果，可以有以下四种因

1、找13元的最少货币数+1，即找13元的方案再加一张10元就是23元了；

2、找18元的最少货币数+1，即找18元的方法再加一张5元就是23元了；

3、找21元的最少货币数+1,21+2=23元

4、找22元的最少货币数+1,22+1=23元

如果假设dp[i]表示要找i元时的最少货币数，则以上四种因对应的公式为

1、dp[23]=dp[13]+1=dp[23-10]+1

2、dp[23]= dp[18]+1=dp[23-5]+1

3、dp[23]=dp[21]+1=dp[23-2]+1

4、dp[23]= dp[22]+1=dp[23-1]+1

四种因中取最小的，即为dp[23]，即找23元时最少的货币数。

而四种因中，dp[22],dp[21],dp[18],dp[13]又是采用同样的方法，求得要找的钱数对应的最小货币数，即迭代。

所以遍历所有的面值(假设i大于所有货币面值)

for j in range(len(arr)):

      dp[i] =min(dp[i],dp[i-arr[j]]+1)

这个min的过程，就是对应上面四种因求最小的过程。

至于为什么初始化dp[]时，让所有dp[i]的初始值为要找的钱数+1,是因为需要判断是否有解，再举个例子：

比如货币面值为3元，要找的钱数为1元,2元时，显然没办法找，当要找的钱数为3元时，恰好1张，当找的钱数为4元时，又无法找开了，所以设置一个值来标记是否能找开的情况。为什么是aim+1呢，因为货币面值是正整数，1是最小的正整数，也就是如果有1元的货币的话，一定能找开，对应的货币数量就是aim本身，所以设置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
        if aim <1:
            return 0
        # dp[i]表示如果要找的钱数为i，对应的最少货币数
        # 初始化，让初始最少货币数为aim+1,以在后面判断是否有解
        dp = [(aim+1) for i in range(aim+1)]
        dp [0] = 0 #要找的钱数为0时，对应的最少货币数为0，显然
        for i in range(1,aim+1):
            for j in range(len(arr)):
                if arr[j]<=i:
                    dp[i] = min(dp[i],dp[i-arr[j]]+1)
        if dp[aim]>aim:
            return -1
        else:
            return dp[aim]