# coding:utf-8
'''有一书店引进了一套书，共有3卷，每卷书定价是60元，书店为了搞促销，推出一个活动，活动如下：如果单独购买其中一卷，那么可以打9.5折。如果同时购买两卷不同的，那么可以打9折。如果同时购买三卷不同的，那么可以打8.5折。如果小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少需要多少钱呢？（x、y、z为三个已知整数）。
'''
prize = 60
x, y, z = 4, 1, 1
money = []
_maxInt = 99999
for i in range(x + 1):money.append([])for j in range(y + 1):money[i].append([_maxInt] * (z + 1))_depNum = 0
def Price(x, y, z):if money[x][y][z] != _maxInt:global _depNum_depNum += 1return money[x][y][z]# 小于0  这次不购买if x < 0 or y < 0 or z < 0:return _maxInt# 只有一本可以买elif (x <= 0 and y <= 0 and z == 1) or (z <= 0 and y <= 0 and x == 1) or (x <= 0 and z <= 0 and y == 1):_min = prize# 两本elif (x <= 0 and y == z == 1) or (y <= 0 and x == z == 1) or (z <= 0 and x == y == 1):_min = prize * 2 * 0.9# 三本elif x == y == z == 1:_min = prize * 3 * 0.85# 比较出每种购买情况中的最小值else:_list = [Price(x - 1, y - 1, z - 1) + prize * 3 * 0.85,Price(x - 1, y - 1, z) + prize * 2 * 0.9,Price(x - 1, y, z - 1) + prize * 2 * 0.9,Price(x, y - 1, z - 1) + prize * 2 * 0.9,Price(x - 1, y, z) + prize * 0.95,Price(x, y - 1, z) + prize * 0.95,Price(x, y, z - 1) + prize * 0.95]_min = min(_list)# 记录已购买的情况中的最小值 减少递归情况money[x][y][z] = _minreturn _minprint(prize * 3 * 0.85 + prize * 3 * 0.95)
print(Price(x, y, z))

边界：只有一本或者两本不同的或者三种不同的

最优子结构：在七种选择中选出最便宜的

状态转移方程式如上