Description

Tom有一个天平秤，和拥有1g、3g、5g、7g类型的砝码无限个数,Tom现在要称重物品，物品重w，
麻烦你告诉Tom，称出这个重量w最少要用到的砝码数量。（设砝码的总重量不超过10000克，且砝码只能放在天平的一端）

Input Format

一个整数w (1<=w<=10000)

Output Format

最少的砝码数量

77

11

Hint

使用穷举，很多小朋友已经发现会超时
可以想一下  我们先计算出
从1g重量最少需要多少砝码
2g重量最少需要多少砝码
3g重量最少需要多少砝码
4g重量最少需要多少砝码 
.....直到我们要计算的w重量
问题演变为怎么样每次算出的砝码是最少的呢
举个例子 我们要知道8g重量时 用到砝码最少
可以把分为 之前的最优的方案+1个
那这个1个 可能为1g 3g 5g 7g 
如果最后加上的砝码是1g 则 7g重量最优方案+1
如果最后加上的砝码是3g 则 5g重量最优方案+1
如果最后加上的砝码是5g 则 3g重量最优方案+1
如果最后加上的砝码是7g 则 1g重量最优方案+1



因为我们之前从1克重量 推演到 w克重量 之间每个的最优方案
必定知道 比8g小的最优方案

Source

动态规划