算法设计,自然数需要几个1表示

问题:使用用最少数量个1，加减乘除括号能够表示1-n自然数的表达式是什么？
比如输入n=10
输出1，1个，1
……
5，5个，1+1+1+1+1
……
10，7个，（1+1+1）×（1+1+1）+1
一开始想法，弄个字典，1按加减乘除组合，得到的新数就插进去，比原先的短就更新。设计个类，有数值结果，需要的个数，表达式，完整表达式，四个属性，重载了加减乘除方法。
这样有问题，不确定需要申请多少空间，不确定更新的终止条件，比如无更新就终止吗？但是新的数是无限的，还有分数，比n大的数可能作为中间结果。分数还可能有误差导致0.33333和0.33334都插进去了
可以先只做n个对象，然后中间结果也只用n以内自然人，除法似乎没用。。。最后检查有没有更短的
最后还是否定这种方案，需要用几个1表示的数用一个集合表示，这些集合组成一个列表
按从小到大的顺序有序增长
比如要得到3个数能表达的集合，只能用集合1和集合2组合