Algorithm analysis

Let $f(n)$ be equal to the smallest number of ones with which you can compose the number $n$. Obviously, $f(1)=1$.

The number 2 can only be represented as the sum of two ones: $2=1+1$. Therefore, $f(2)=2$. The number 3 can only be represented as the sum of three ones: $3=1+1+1$. Therefore, $f(3)=3$.

The number 4 can be represented either as $4=1+1+1+1$, or $4=(1+1)\ast (1+1)$. However, in both cases, 4 ones are used. Therefore, $f(4)=4$.

Consider the sought expression, the result of which equals $n$.

Suppose the last operation performed in it was addition. For example, let the first addend $i$ consist of $f(i)$ ones, and the second addend $n-i$ consist of $f(n-i)$ ones. The value of $i$ should be chosen such that the sum $f(i)+f(n-i)$ is minimal.

At the same time, it is enough to iterate the value of $i$ up to $n/2$, since it can be assumed that the first addend is not greater than the second. Thus, the following relationship holds:

Suppose the last operation performed in it was multiplication. For example, let the first factor $i$ consist of $f(i)$ ones, and the second factor $n/i$ consist of $f(n/i)$ ones. This case occurs if $n$ is divisible by $i$.

The value of $i$ should be chosen such that the sum $f(i)+f(n/i)$ is minimal. It is enough to iterate the value of $i$ from 2 to $\sqrt{n}$. The following relationship holds:

Thus

Example

Let's calculate the answer for $n=7$:

$f(7)=f(6)+f(1)=(f(2)+f(3))+f(1)=2+3+1=6$

The number 7 can be represented by 6 ones, namely:

$7=(1+1)\ast (1+1+1)+1$

int res[5001];
scanf("%d",&n);
res[1] = 1;

for(i = 2; i <= n; i++)
{
  res[i] = i;
  for(j = 1; 2 * j < i; j++)
    if (res[j] + res[i-j] < res[i]) res[i] = res[j] + res[i-j];
  for(j = 2; j * j <= i; j++)
    if (i % j == 0) 
      if (res[j] + res[i/j] < res[i]) res[i] = res[j] + res[i/j];
}
printf("%d\n",res[n]);