Given those 3 valid operations over numbers and an integer $n$:
- add $1$ to the number
- multiply the number by $2$
- multiply the number by $3$
describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.
For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.
I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.
d=dict() def to(x,num,di): if (num==x): return 0 elif (num>x): return num elif num in di: return di[num] else: if num+1 not in di: di[num+1]=to(x,num+1,di) if num*2 not in di: di[num*2]=to(x,num*2,di) if num*3 not in di: di[num*3]=to(x,num*3,di) di[num]=min(di[num+1],di[num*2],di[num*3])+1 return di[num] return to(n,1,d)
I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.