値がそれぞれ \(a,b\) であるような \(2\) つの数式 \(s,t\) に対して，次のような文字列も数式として有効です．（+ は文字列の結合を表します．）

• ( + \(s\) + ) （値は \(a\)）
• \(s\) + + + \(t\) （値は \(a+b\)）
• \(s\) + * + \(t\) （値は \(a\times b\)，ただし \(s,t\) はともに <term> である必要がある）

これらの構成ルールをもとに，値が \(N\) になるような最短の数式を dp で求めます．ここで

• \(dp1[i]\) を値が \(i\) となる数式のうち，長さが最小のもの
• \(dp2[i]\) を値が \(i\) でとなる <term> を満たす数式のうち，長さが最小のもの

と定義します．

まず，1 のみで表現できる値については，次のように初期化できます：

• \(dp1[i]=dp2[i]=\) 11...1

遷移は以下の通りです（\(\leftarrow\) は，矢印の左辺の数式を，右辺の数式で更新できる場合を表します．すなわち，右辺の方が文字列として短い場合に更新します）：

• \(dp1[i] \leftarrow dp1[j]\) + + + \(dp1[k]\;(j+k=i)\)
• \(dp1[i] \leftarrow dp2[j]\) + * + \(dp2[k]\;(j\times k=i,j\neq 1,k\neq 1)\)
• \(dp2[i] \leftarrow\) ( + \(dp1[j]\) + + + \(dp1[k]\) + ) \(\;(j+k=i)\)
• \(dp2[i] \leftarrow dp2[j]\) + * + \(dp2[k]\;(j\times k=i,j\neq 1,k\neq 1))\)

各数式の長さは \(O(\log N)\) であることが証明できるので，この dp は \(O(N^2 \log N)\) で動作します．また，dp で文字列そのものではなく長さの最小値を持つと計算量は \(O(N^2)\) になります．