Background
Challenge is inspired by this question.
The 1-expression is a formula that in which you add and multiply the number 1 any number of times. Parenthesis is allowed, but concatenating 1's (e.g. 11) is not allowed.
Here is an example to get the 1-expression for \$19\$:
(1+1)*(1+1)*(1+1+1+1)+1+1+1 = 19
Total number of \$1\$'s is \$11\$ but there is shorter than this:
(1+1)*(1+1+1)*(1+1+1)+1 = 19
Total number of \$1\$'s is \$9\$.
Program
Given a positive integer n
output the minimum 1's to get the 1-expression for n
.
Notes:
Test cases
Input -> Output | 1-Expression
1 -> 1 | 1
6 -> 5 | (1+1+1)*(1+1)
22 -> 10 | (1+1)*((1+1+1+1+1)*(1+1)+1)
77 -> 14 | (1+1)*(1+1)*((1+1+1)*(1+1+1)*(1+1)+1)+1
214 -> 18 | ((((1+1+1)*(1+1)*(1+1)+1)*(1+1)*(1+1)+1)*(1+1)+1)*(1+1)
2018 -> 23 | (((1+1+1)*(1+1)+1)*(1+1+1)*(1+1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1)*(1+1)