ABC188 F +1-1x2
操作を逆から考える. すると, +1と-1の操作は同じだが, *2の操作が/2(ただし元の数が偶数の時のみ) となる. このような操作を行って$ Yから$ Xにするための最小回数は, 再帰を用いて求めることができる.
具体的には次のような場合分けをする.
$ f(y) := $ yから$ Xにするための最小の操作回数 とする.
$ y = 1のとき
$ |X-y|が答え.
$ y \% 2 = 0のとき
$ min(|X-y|, f(y/2) + 1)が答え.
それ以外のとき
$ min(|X-y|, f(y - 1) + 1, f(y + 1) + 1)が答え.
あとはこれをメモ化することで解ける.