动态规划.md

什么是动态规划？动态规划的意义是什么？ - 阮行止的回答 - 知乎

# -*- coding: utf-8 -*-

# 总金额
money = 2000
# 存储金额与使用数量的数组
f = [0] * money
# 金额为零时可用策略为零
f[0] = 0

fmt = 'f[{:0>' + str(len(str(money))) + '}] = {}'

for i in range(1, money):
    cost = float('inf')
    if i >= 1:
        cost = min(cost, f[i - 1] + 1)
    if i >= 5:
        cost = min(cost, f[i - 5] + 1)
    if i >= 11:
        cost = min(cost, f[i - 11] + 1)
    f[i] = cost

    print fmt.format(i, f[i])