[Question]
  [
# Introduction
Your goal is to find the least number of ones you need to add or multiply together to get the input value, this is [A005245](//oeis.org/A005245).
## Input
One positive integer ***N***.
## Output
The smallest number of ones that must be added/multiplied to get ***N***.
### Sample Input
> 
> 7
> 
> 
> 
### Sample Output
> 
> 6
> 
> 
> 
### Explanation
> 
> (`1` + `1` + `1`) \* (`1` + `1`) + `1` = 7
> 
> 
> Because this requires `6` ones, the output is `6`
> 
> 
> 
### Test cases
```
 1  1
 2  2
 3  3
 5  5
10  7
20  9
50 12
```
As this is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge, lowest number of bytes wins.
  
[Answer]
# [Python 2](https://docs.python.org/2/), ~~74~~ 70 bytes
```
f=lambda n:min([n]+[f(j)+min(n%j*n+f(n/j),f(n-j))for j in range(2,n)])
```
[Try it online!](https://tio.run/##LY/BasMwEETP1lcMFBNtrFBHpRdDesxPhBxcJLUS9SqoCqQt/XZ3FXoaZnZ3Hnv5qu@Z7bqGw8e8vLoZPC2R9YnPwynoRENz3KctD0HzYyIjsktEIRckREaZ@c1ra5jOtDofUP1n1dsbTaprS9yWbmK6S4lcsentFbsXiGzQQ7OBVBIpdT/cG1iDJ4Nng/0o6QMWv@T4PdeYWTVAaDdHHBAMnMjPb2PFICjOteHcBCcvyOwo1aorvl4L37N/jB2FMNL6Bw "Python 2 – Try It Online")
### Alternate version, 59 bytes (unverified)
```
f=lambda n:min([n]+[f(j)+f(n/j)+f(n%j)for j in range(2,n)])
```
This works at least up to **n = 1,000,000**, but I have yet to prove that it works for all positive **n**.
[Try it online!](https://tio.run/##LY7BbsIwEETP8VeMhCJsMCK46iUSPfITiEOQ7dYRWSPXkQJVvz2sgdNod2fm7fWWfyKZefb7SzecbQdqh0DySKf10cterb2k7UvqXvmY0CMQUkffThpN6qRm6zyy@81yNalWVMVExTTxUF1ToIxlbUZsvsCyRA1JGtyolBDP4E7DaHxofGrsGt4uMLghhnuXQyRRAL5kDtjDa1iWv//CCp5RFHPB2RaW/@bbgatFlVweEz13b4xpmNCo@QE "Python 2 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~16~~ 14 bytes
Thanks Dennis for saving 2 bytes!
```
ÆḌḊ,Ṗß€€+U$FṂo
```
[Try it online!](https://tio.run/##y0rNyan8//9w28MdPQ93dOk83Dnt8PxHTWuASDtUxe3hzqb8////GxoAAA "Jelly – Try It Online")
---
## Logic explanation
Given a number **n**:
* If it's `1`, the answer is `1`. Otherwise:
The representation is either `a + b` or `a × b`, where `a` and `b` are expressions.
Consider all possible values of `a` and `b`:
* If the representation is `a + b`, then `a` and `b` are in range `[1 .. n-1]`.
* If the representation is `a × b`, `a` and `b` are proper divisors of `n` larger than `1`.
In both cases, the list `[[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]` is computed (`ÆḌḊ,Ṗ`), map the current link over each number `ß€€`, add the correct pairs together (`+U$`) and get the minimum value (`FṂo`).
## Code explanation
```
ÆḌḊ,Ṗß€€+U$FṂo   Main link. Assume ***n*** = 10.
ÆḌ       Proper **d**ivisors. *[1,2,5]*
  Ḋ      **Ḋ**equeue, remove the first element. *[2,5]*
   ,Ṗ    Pair with **Ṗ**op. Auto convert ***n*** = 10 to range 
         *[1,2,3,4,5,6,7,8,9,10]* and remove the last element
         *10*, get *[1,2,3,4,5,6,7,8,9]*.
ß€€      Apply this link over each element.
   +U$   Add with the **U**pend of itself.
FṂ       **F**latten and get the **Ṃ**inimum element.
  o      Logical **o**r with ***n***.
         If the list is empty, minimum returns *0* (falsy), so logical or
         convert it to ***n***.
```
[Answer]
## JavaScript (ES6), ~~108~~ 96 bytes
```
f=n=>n<6?n:Math.min(...[...Array(n-2)].map((_,i)=>Math.min(f(++i)+f(n-i),n%++i/0||f(i)+f(n/i))))
```
Very inefficient; `Array(n>>1)` speeds it up slightly at a cost of a byte. Explanation: `n%++i` is non-zero if `i` is not a factor, so `n%++i/0` is `Infinity` (and therefore truthy, and also definitely not minimal) if `i` is not a factor, but `NaN` (and therefore falsy) if `i` is a factor. Edit: Saved 12 bytes with inspiration from @edc65.
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 66 bytes
A port of [Dennis's Python answer](https://codegolf.stackexchange.com/a/154240/9288):
```
f(n)=vecmin(concat(n,[f(j)+min(n%j*j+f(n\j),f(n-j))|j<-[2..n-1]]))
```
[Try it online!](https://tio.run/##FY3BCoMwEER/ZSkUdjUrjefaH4keJJiSha4hSE/@e1wv82B4zJS1Zv6W1hIqTf8t/rJi3DWuB6oLCYX6u9KndNKbNAs5AwvRKW8O4zAo@2UhammvqDCBd@BfDkrNaiPwAP5Y3AcmXQ "Pari/GP – Try It Online")
---
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 72 bytes
Longer, but more efficient:
```
f(n)=if(n<6,n,vecmin([if(d>1,f(d)+f(n/d),1+f(n-1))|d<-divisors(n),d<n]))
```
[Try it online!](https://tio.run/##Tc2xDsJACAbg3acgTkfk4jHU6doXMQ5GrGGQXq5NJ9/9pDFRlz/wEaBcq8ZHaW0Mhr165hMZrffbUy2cHWRg8sSDz46CxFsRGfElOYquOk919mWSbBfENk41GPTABJwISlVbHPYQB4/tDeLuo136cZe@zOnPvfGjbw "Pari/GP – Try It Online")
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 213 bytes
**Edit:** I've been [severely beaten](https://codegolf.stackexchange.com/a/154244/61563).
```
f(n)={d;n<6&return(n);if(n<=#a,a[n]&return(a[n]),a=vector(n));for(i=1,n-1,a[i]||a[i]=f(i));a[n]=min(vecmin(vector(n\2,k,a[k]+a[n-k])),if(isprime(n),n,vecmin(vector((-1+#d=divisors(n))\2,i,a[d[i+1]]+a[d[#d-i]]))))}
```
[Try it online!](https://tio.run/##VY3BDoIwDIYfhsSsoTtMoxfYk@AOi2OmIRQykIv47LMzevCyLn@//@vsE@n7nHNUDPYZGm4vh9Svj8QSNCRxayuPvmP3y8sf0Nutv61TEgyaKJOsQdZGUHL7Xl4bFcmy8HYkVlL4jk/vesRB6MHVQujBAaDco2VONPaiRcb/htKmroINtNEypaVcFgeJI3RUG1dEoauCJicygFcWFa8qqvMJIL8B "Pari/GP – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 181 bytes
```
def F(N,n,s="",r=""):
 try:
	if n<1:return(eval(s)==N)*0**(`11`in s or"**"in s)*s
	for c in"()+*1":r=F(N,~-n,s+c)or r
 except:r
 return r
f=lambda N,n=1:F(N,n).count(`1`)or f(N,-~n)
```
[Try it online!](https://tio.run/##JY69DsIwDIRn@hRWpjgERPhZIrIy9hlaSiIqgVu5AcHCqxcHFut0Z/u78Z2vA23n@RITnHRtyU5BKcsy0FeQ@e2rRZ@Ajs5zzA8mHZ/tTU8YQo1mY4xunGt6ggkGVsaoItFM1SINDB30pDQujVOeQwF8VoJYdighVxBfXRyzF/V/Ll4Kt/Z@vrQgZYLzv1K47oYHZUE15TCJt/oQzgVRCwK0s7C1sLOwt3BADyP3lMsizl8 "Python 2 – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 59 bytes
Saved 3 bytes thanks to Martin Ender. Using CP-1252 encoding, where `±` is one byte.
```
±1=1;±n_:=Min[1+±(n-1),±#+±(n/#)&/@Divisors[n][[2;;-2]]]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78///QRkNbQ@tDG/PirWx9M/OiDbUPbdTI0zXU1Dm0URnM1lfWVNN3cMksyyzOLyqOzouNjjayttY1io2N/e@SHx1QlJlXEp2no6CkoGunoKSjADQrVkehGihiCEQGtbHWXBA1pgbIikwN4BKGBigyQG6s9X8A "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/), -p 78 bytes
79 bytes in old style counting (`+1` for `-p`)
The fact that perl must use an extra `$` for all scalar access really hurts the length of golfs that do a lot of arithmetic...
This method is mostly like the others already posted (try multiplication and addition to build a target number, take the cheapest). It however doesn't repeatedly recurse down so it can be used for relatively large inputs.
It also doesn't try to minimize the cost of building a number by addition or multip[lication because perl 5 has no builtin `min` and numeric sort is looooooong (as seen from the sort still in the code). Instead I just assume if a number is a factor of the target that I will use multiplication. That is safe since if e.g. `3` is a factor of `12` (so it sums the cost of `3` and `12/3`) later in the loop it will consider `9=12-3` which will not be a factor, so `9+3` with the same cost as `3+9` will get tried anyways. However that may fail for targets `<= 4` (it only does for `1` and `2`). Adding `$_` to the list to minimize fixes that. Which is unfortunate since I don't actually need that for the base cases because I already initialize `@;` with the proper starting values so it costs 3 bytes.
```
#!/usr/bin/perl -p
($_)=sort{$a-$b}$_,map{$;[$_]+$;[$'%$_?$'-$_:$'/$_]}//..$_ for@;=0..$_;$_=pop@
```
[Try it online!](https://tio.run/##FchBCsIwEEbhq3TxSxSbZLroxhDsPUSGChUEdYakrkqv7mhX7@PpVJ69ferU9KGjQMn24EOuUuYFo8dtBbevURekC/h63OJ24DOcB5/g4v@uMYYAbu5ShpRpcwJnFR3MOiL6is4PeVfz@gM "Perl 5 – Try It Online")
]