兑换零钱(一)——python

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

该题类似于跳台阶，区别在于不是每一种跳法都能抵达下一级台阶，所以Dp数组初始值不能设为0，要设为最大值AIM+1，这样才能在转移数组中排除这些选项。如果没有兑换方法，那么最后结果就是aim+2，所以如果dp[aim] > aim返回-1.

def minMoney(arr , aim ):
        # write code here
        if aim < 1:
            return 0;
        if len(arr)==0:
            return -1
        dp = [aim+1 for i in range(aim+1)]
        dp[0]=0
        for i in range(min(j for j in arr),aim+1):
            dp[i]=min(dp[i-j] for j in arr if j<=i)+1
        if dp[aim]>aim:
            return -1
        return dp[aim]