题解 | #小招喵跑步#

import sys
for line in sys.stdin:
    #这里面2n到达的位置应该是唯一可能会导致往后走步数还能减少的情况
    n=int(line)
    if n<0:
        n=-n
    dp=[i for i in range(n+2)] # 一开始都给一个很大的数
    if n==0:
        print(0)
    elif n==1:
        print(1)
    elif n==2:
        print(2)
    else:
        dp[0]=0
        dp[1]=1
        dp[2]=2
        for i in range(1,n+1):
            # 分奇偶讨论
            if i%2: # 如果为奇数
                dp[i]=min(dp[i-1],dp[i+1])+1
                if 2*i<=n+1:
                    dp[2*i]=dp[i]+1
            else: # 如果是偶数，后面的奇数位置不可能比他好，所以只考虑两种情况
                dp[i]=dp[i//2]+1
                if 2*i<=n+1:  # 进一步更新下一个2倍的值（用于奇数位置的计算）
                    dp[2*i]=dp[i]+1
        print(dp[n])

这里面需要考虑两种情况：偶数还是奇数。

主要限制住dp的原因是他可以从n+1到n。

那么直接分情况讨论，n为偶数的时候，dp[n/2]+1就是最优值了，此时顺带着可以计算一下2n的值。

（因为假设n=2a，n+2=2b，那么可以推出来b=a+1. 那么dp[a]的值至多比dp[b]多1，进而dp[2b]至多比dp[2a]少2，那么从2a直接得到的最优值，不会再更好了,类似的可以推出来dp[2a]和dp[2a-1]至多差1，也就是没法从前面的元素得到优化了）

奇数，就直接算前后偶数取最小。因为后面出现的偶数也已经计算完了，所以可以直接从前往后算。

额外需要注意的就是负数的情况。一开始取一个绝对值就好了。