Starting from an integer $n >0$, iterate the two operations of substracting one and dividing by $2$ (when the number is even) until $1$ is reached. Thus when the number is odd we can only substract $1$, but when the number is even we may apply either of the two operations. Denote by $f(n)$ the minimal number of steps needed to reach $1$ from $n$. Thus $f(1)=0$ and
$$ f(n)=\left\lbrace \begin{array}{lcl} 1+{\textsf{min}}(f(m),f(2m-1)), &\text{when}& n \text{ is even}, n=2m,\\ 1+f(n-1) &\text{when}& n \text{ is odd}. \end{array}\right. \tag{1} $$
The natural, “greedy” way to proceed is to always divide by $2$ when the number is even and substract $1$ otherwise. I have checked up to $n=10^6$ that this "greedy" strategy is the unique optimal solution ; in other words, we always have $f(m)<f(2m-1)$ for $m>1$ in the first line of $(1)$. In fact, it seems that if we decompose $m$ as $2^i(2j+1)$ where $i$ and $j$ are nonnegative integers, then
$$ f(2m-1)-f(m)=\left\lbrace \begin{array}{lcl} i &\text{when}& j=0,\\ i+1 &\text{when}& j>0. \end{array}\right. \tag{2} $$
Although my impression is that there is probably a simple way to show (2) by induction, and perhaps a simple interpretation of $f(n)$ in the vein of “the number of ones in the dyadic decomposition on $n$”, I was unable to find it. Any ideas? Is this perhaps already known ?