For two expressions \(s\) and \(t\) that evaluate to \(a\) and \(b\), respectively, the following strings are also valid expressions. (“+” denotes a string concatenation.)

• ( + \(s\) + ) (evaluates to \(a\))
• \(s\) + + + \(t\) (evaluates to \(a+b\))
• \(s\) + * + \(t\) (evaluates to \(a\times b\). \(s\) and \(t\) both need to be <term>)

Under these construction rules, we seek for the shortest expression that evaluates to \(N\) with DP (Dynamic Programming). Define

• \(dp1[i]\): shortest expression that evaluates to \(i\), and
• \(dp1[i]\): shortest expression that is eligible as <term> and evaluates to \(i\).

Values that can be represented as repeated 1s can be initialized as:

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

The transitions are as follows. (\(\leftarrow\) is executed only when applicable; in other words, only when the right-hand-side string is shorter.)

• \(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))\)

One can prove that each expression has an \(O(\log N)\) length, so this DP runs in \(O(N^2 \log N)\) time. If we maintain the shortest length instead of the string itself in DP, the complexity reduces to \(O(N^2)\).