如何使用符号+*()和1以最小的成本表示整数?

user2807293 19 algorithm math dynamic-programming

任务是从符号+ * ( )(加法,乘法和括号)和数字构建整数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 

Paul Hankin.. 8

您可以为每个数字i <n使用动态编程和计算,计算i的最短表达式,以及计算可以在乘法上下文中使用的i的最短表达式.一般来说,第二个表达式会比第一个表达式长:例如2可以构造为'1 + 1',但如果你想在乘法中得到'2',那么它将是'(1 + 1)'.

这里有一些未经优化的代码,可以为所有数字打印最短的解决方案.它在我的笔记本电脑上运行的时间超过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])