题解 | #换钱的最少货币数#

'''
解题思路：
动态规划
1.dp[i]定义
钱数目标值为i的最少货币数
2.状态转移方程
设目标值为aim，对于所有的i初始化 dp[i]=aim+1 ,长度为 aim+1。对于指定的i,遍历所有钱币arr[j]
当 arr[j]<=i 时，dp[i] = min(dp[i], dp[i-arr[j]]+1), 典型的背包问题思路：即减去一个币值，加上一张
最后当 dp[-1]!=aim+1 时，返回 dp[-1]
3.边界
dp[0] = 0
#=============================================================================================
'''
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        #print(arr)
        #print(aim)        
        dp = [aim+1]*(aim+1)                 # 把dp数组全部定为最大值
        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)
        #print(dp)
        if dp[-1]==aim+1:
            return -1
        else:
            return dp[-1]
        
#Solution().minMoney([5,2,3], 20)