猫史档案馆

【问题】

在互联网不发达的时候，人们传递信息是通过邮局寄信，寄信需要购买邮票来支付邮费。阿短家里有一本集邮册，收集了各式各样不同的邮票。他拿出40张2分钱邮票、30张4分钱邮票、20张6分钱邮票、10张8分钱和5张10分的邮票，想要试试用这些邮票中的一张或若干张可以得到多少种不同的费用。
请使用Python代码帮阿短计算一下，一共有多少种不同的费用吧。使用print()函数将组合的总数显示出来。

【思路】

刚看见这道题想用喵递归求解，无非就是40个2、30个4、30个6、10个8和5个10 这些数取几个数相加得到和的数量，每个数都有两种状态，用或是不用。但是仔细一想不对，数据规模有点大，用喵递归即使用上记忆化搜索，时间复杂度都会非常高，所以还得另想他法。

换个角度思考，我可以选择用不用2分钱邮票，如果用的话都用几张，所以我把只用2分钱所有的可能放在一个列表中，只用4分钱、6分钱、8分钱、10分钱分别放在一个列表中，然后循环遍历出所有可能。把所有的可能放在set中去重，最后set的长度-1就是答案。（-1是为了减去0，即没用邮票的可能）

【代码】

if __name__ == '__main__':
    # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 喵, 66, 68, 70, 72, 74, 76, 78, 80]
    l2 = [i * 2 for i in range(41)]
    # [0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 喵, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120]
    l4 = [i * 4 for i in range(31)]
    # [0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 102, 108, 114, 120]
    l6 = [i * 6 for i in range(21)]
    # [0, 8, 16, 24, 32, 40, 48, 56, 喵, 72, 80]
    l8 = [i * 8 for i in range(11)]
    # [0, 10, 20, 30, 40, 50]
    l10 = [i * 10 for i in range(6)]
    
    s = set()
    for i in l2:
        for j in l4:
            for x in l6:
                for y in l8:
                    for z in l10:
                        s.add(i + j + x + y + z)
    res = len(s) - 1
    print(res)