<分区>
任务是从符号 + * ( )(加法、乘法和括号)和数字 1 构建整数。给定一个整数，并且必须使用最少的字符数输出一个表达式。例如:
4 = 1+1+1+1
23 = 11+11+1
242 = (11+11)*11
1000 = 1+(1+1+1)*(1+1+1)*111
1997 = (1+1)*(1+1+1)*111+11*11*11
<分区>
任务是从符号 + * ( )(加法、乘法和括号)和数字 1 构建整数。给定一个整数，并且必须使用最少的字符数输出一个表达式。例如:
4 = 1+1+1+1
23 = 11+11+1
242 = (11+11)*11
1000 = 1+(1+1+1)*(1+1+1)*111
1997 = (1+1)*(1+1+1)*111+11*11*11
最佳答案
您可以使用动态规划，并为每个数字 i < n 计算计算 i 的最短表达式，以及计算 i 的可用于乘法上下文的最短表达式。一般来说，第二个表达式会比第一个长:例如 2 可以构造为“1+1”，但如果你想在乘法中使用“2”，那么它将是“(1+1)”。
这是一些未优化的代码，它打印出所有数字的最短解决方案，直到 2000。它在我的笔记本电脑上运行了 2 秒多一点，但是从代码中删除所有字符串构造的范围很大。它运行时间为 O(n^2)。
def getbest(a, b):
return a or b if not (a and b) else min((a, b), key=len)
def minconstruct(n):
res = [[None, None] for _ in range(n + 1)]
for i in xrange(1, n + 1):
if set(str(i)) == set('1'):
res[i][0] = res[i][1] = str(i)
for j in xrange(1, i // 2 + 1):
sol = '%s+%s' % (res[j][0], res[i-j][0])
res[i][0] = getbest(res[i][0], sol)
res[i][1] = getbest(res[i][1], '(' + sol + ')')
for j in xrange(2, i):
if i % j != 0:
continue
sol = '%s*%s' % (res[j][1], res[i//j][1])
res[i][0] = getbest(res[i][0], sol)
res[i][1] = getbest(res[i][1], sol)
return res
r = minconstruct(2000)
for i, x in enumerate(r[1:]):
print '%4d: %s' % (i, x[0])
关于algorithm - 如何以最小的成本使用符号 + * () 和 1 来表示整数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19473847/