设置一个 dp 数组，从 2 到 n 都扫一遍，核心代码如下：

dp[1] = 0;
for (int i=2; i<=n; i++)
{
    if (i%2==0)
        dp[i] = min(dp[i-1]+1, dp[i/2]+1);
    else dp[i] = dp[i-1] + 1;
    dp[i-1] = min(dp[i-1], dp[i]+1);
}

然后用 O( N )的时间复杂度就可以出解了。