Question

К начальному числу единице можно прибавить единицу, умножить на два, умножить на три. На каждом последующем шаге можно выполнять только эти три операции. Определить за какое минимальное число шагов можно достичь произвольно введенного числа N.

До предела умножать на три , потом на два и добавлять единицами не оптимальный к сожалению алгоритм.

Нужна либо формула, либо алгоритм (словами ! ) , либо программа на Питон.

Answer 1

N = int(input())

dp = [100000000 for i in range(N + 2)]

dp[1] = 0

for i in range(2, N + 1):

    dp[i] = dp[i - 1] + 1

    if i % 2 == 0 and dp[i // 2] != 100000000:

       dp[i] = min(dp[i], dp[i // 2] + 1)

    elif i % 3 == 0 and dp[i // 3] != 100000000:

       dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[N])