操作を逆から考えると、以下のような問題になります。

以下の \(3\) 種類の操作で \(Y\) を \(X\) にするのに必要な最小の操作回数を求めよ。

• タイプ \(1\) : \(Y\) に \(1\) を足す
• タイプ \(2\) : \(Y\) から \(1\) を引く
• タイプ \(3\) : (\(Y\) が \(2\) で割り切れるときに限る) \(Y\) を \(2\) で割る

ここで、タイプ \(1\) とタイプ \(2\) が連続して現れることはないとしてよいことは明らかです。
また、\(k (k \ge 2)\) 回 \(1\) を足してから \(2\) で割るよりも、\(k - 2\) 回 \(1\) を足してから \(2\) で割り、\(1\) 回 \(1\) を足した方が、同じ結果で操作回数が少ない (引く操作についても同様) ため、最後のタイプ \(3\) の操作の後を除いては、タイプ \(1\) 同士やタイプ \(2\) 同士も連続しないとしてよいことが分かります。
逆に、最後のタイプ \(3\) の操作を終えた時点で \(Y = y\) のとき、必要な残りの操作回数は \(|X - y|\) と確定します。

以上を踏まえて以下のような再帰関数を考えます。

\(\mathrm{solve}(y)\) : \(Y = y\) の時の答え
\(\mathrm{solve}(y) = \)

• \(y = 1\) のとき : \(|X - y|\)
• \(y\) が \(1\) 以外の奇数の時 : \(\min(|X - y|, \mathrm{solve}(\frac{y + 1}{2}) + 2, \mathrm{solve}(\frac{y - 1}{2}) + 2)\)
• \(y\) が偶数の時 : \(\min(|X - y|, \mathrm{solve}(\frac{y}{2}) + 1)\)

これを \(y\) についてメモ化し、\(\mathrm{solve}(Y)\) を呼ぶと答えが求まります。

計算量を考えましょう。
\(\mathrm{solve}(Y)\) から呼ばれる \(\mathrm{solve}(y)\) の \(y\) の種類数を考えます。
\(\mathrm{solve}(Y)\) の呼び出しを \(0\) 段目の再帰とみなしたとき、\(d\) 段目の再帰での \(y\) は以下を満たします。

• (毎回 \(\mathrm{solve}(\frac{y - 1}{2})\) という形での再帰が繰り返されたときを考えると) \(y \ge \frac{\frac{\frac{Y - 1}{2} - 1}{2} - 1}{2}_\ddots\) (\(d\) 段) \( = \frac{Y}{2^d} - \sum_{i = 1}^d \frac{1}{2^d} \gt \frac{Y}{2^d} - 1\)
• (毎回 \(\mathrm{solve}(\frac{y + 1}{2})\) という形での再帰が繰り返されたときを考えると) \(y \le \frac{\frac{\frac{Y + 1}{2} + 1}{2} + 1}{2}_\ddots\) (\(d\) 段) \( = \frac{Y}{2^d} + \sum_{i = 1}^d \frac{1}{2^d} \lt \frac{Y}{2^d} + 1\)

よって各段ごと、に呼び出される \(y\) は高々 \(2\) 個 (定数個) であることが分かります。
段数は \(O(\log(Y))\) 個しかありませんから、メモ化に \(O(1)\) のハッシュマップ等を使うことにすると、計算量は \(O(\log(Y))\) です。