algorithm - 最小限のコストで記号 + * () と 1 を使用して整数を表現する方法は?

Question

+ * ( )タスクは、記号(加算、乗算、括弧) と数字から整数を構築すること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 

Answer 1

動的計画法を使用して、各数値 i < n について、i を計算する最短の式と、乗算コンテキストで使用できる i を計算する最短の式を計算できます。一般に、2 番目の式は最初の式よりも長くなります。たとえば、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])