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

关键还是在于找到状态转移方程，设dp[i]为i块钱最少需要几张货币来兑换，于是可以想到状态转移方程为：

$dp[i]=min(dp[i-arr[j]])+1,\mathrm{对}\mathrm{于}\mathrm{任}\mathrm{意}\mathrm{的}j,ifinotinarrdp[i]=min(dp[i-arr[j]])+1,\; 对于任意的j,if\; \backslash \; i\; \backslash \; not\; \backslash \; in\; \backslash \; arr$

$dp[i]=1,ifiinarrdp[i]=1,if\; \backslash \; i\; \backslash \; in\; \backslash \; arr$

设最小的面试的货币是minv，也就是需要从minv遍历到aim，因为小于minv的aim是不可能兑换成功的。

此外注意下边界条件就可以了，代码如下：

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

arr = [5,2,3]
aim = 20
print(Solution().minMoney(arr,aim))