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

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#

# 注意：这道题边界条件很有意思
class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        ##init
        
        dp = [float('inf') for i in range(0, aim + 1)]
        dp[0] = 0
        ##process
        if aim <= 0:
            return 0
        ret = -1
        for i in range(0, len(arr)):
            cur_coin = arr[i]
            for j in range(1, aim + 1):
                if cur_coin > j:
                    continue 
                #用或者不用
                dp[j] = min(dp[j], dp[j - cur_coin] + 1)
        print ("dp: ", dp)
        if dp[aim] != float('inf'):
            ret = dp[aim]
        return ret