Аналіз алгоритму

Нехай $f(n)$ дорівнює найменшій кількості одиниць, за допомогою яких можна скласти число $n$. Очевидно, що $f(1)=1$.

Число 2 можна представити тільки як суму двох одиниць: $2=1+1$. Тому $f(2)=2$. Число 3 можна представити тільки як суму трьох одиниць: $3=1+1+1$. Тому $f(3)=3$.

Число 4 представимо або у вигляді $4=1+1+1+1$, або $4=(1+1)\ast (1+1)$. Однак у обох випадках використовується 4 одиниці. Отже $f(4)=4$.

Розглянемо шукане вираз, результат якого дорівнює $n$.

Нехай останньою виконаною в ньому операцією було додавання. Нехай, наприклад, перше доданок $i$ складається з $f(i)$ одиниць, а друге доданок $n-i$ складається з $f(n-i)$ одиниць. Значення $i$ слід вибрати таким, щоб сума $f(i)+f(n-i)$ була мінімальною.

При цьому значення $i$ достатньо перебирати до $n/2$, оскільки можна припустити, що перше доданок не більше другого. Таким чином, має місце співвідношення:

Нехай останньою виконаною в ньому операцією було множення. Нехай, наприклад, перший множник $i$ складається з $f(i)$ одиниць, а другий множник $n/i$ складається з $f(n/i)$ одиниць. Цей випадок має місце, якщо $n$ ділиться націло на $i$.

Значення $i$ слід вибрати таким, щоб сума $f(i)+f(n/i)$ була мінімальною. Значення $i$ достатньо перебирати від 2 до $\sqrt{n}$. Має місце співвідношення:

Таким чином

Приклад

Вирахуємо відповідь для $n=7$:

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

Число 7 можна представити 6 одиницями, а саме:

$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]);