Function ChangeMaking

Dynamic Programming.py:4–12

(coinVal, change)

# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
def ChangeMaking(coinVal, change):
    alist = [0]*(change+1)
    for i in range(1, change+1):
        temp = change; j = 0
        while j <= len(coinVal)-1 and i >= coinVal[j]:
            temp = min(alist[i-coinVal[j]], temp)
            j += 1
        alist[i] = temp + 1
    return alist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))