\({} \mathrm{expr}[n], \mathrm{term}[n], \mathrm{factor}[n], \mathrm{number}[n] \) を「評価した値が \(n\) になる文字列で，対応する BNF を満たすもののうち最短のもの」とします（存在しない場合は適宜処理する）．

\(\mathrm{number}[n]\) は簡単に前計算できます．

\(n=1,2,\dots,N\) について順に \(\mathrm{expr}[n],\mathrm{term}[n],\mathrm{factor}[n]\) を計算します．

以下の形の遷移については，すでに計算済みの値しか用いる必要がないため素直に書けばよいです．

• <expr> \(\leftarrow\) <expr> "+" <term>
• <term> \(\leftarrow\) <term> "*" <factor>
• <factor> \(\leftarrow\) <number>

少し考えなければならないのが以下の形の遷移です．

• <expr> \(\leftarrow\) <term>
• <term> \(\leftarrow\) <factor>
• <factor> \(\leftarrow\) "(" <expr> ")"

これらは循環する形になっており，困りそうです． しかし実はこの遷移をそのまま書いたものを2回反復すればよいです（更新されるとしたらどのような形の文字列になるかを考えればよい）．

実装例(Python)

N = int(input())

expr = [None] * (N + 1)
term = [None] * (N + 1)
factor = [None] * (N + 1)
number = [None] * (N + 1)

i = 1
while i <= N:
  number[i] = str(i)
  i = i * 10 + 1

for n in range(1, N + 1):
  for x in range(1, n):
    new = f'{expr[x]}+{term[n-x]}'
    if expr[n] is None or len(expr[n]) > len(new):
      expr[n] = new

  for x in range(2, n):
    if n % x == 0:
      new = f'{term[x]}*{factor[n//x]}'
      if term[n] is None or len(term[n]) > len(new):
        term[n] = new
  
  if number[n] is not None:
    factor[n] = number[n]
  
  for _ in range(2):
    if term[n] is None or (factor[n] is not None and len(term[n]) > len(factor[n])):
      term[n] = factor[n]
    if expr[n] is None or (term[n] is not None and len(expr[n]) > len(term[n])):
      expr[n] = term[n]
    if factor[n] is None or (expr[n] is not None and len(factor[n]) > len(expr[n]) + 2):
      factor[n] = f'({expr[n]})'

print(expr[N])