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,也就是没法从前面的元素得到优化了)
奇数,就直接算前后偶数取最小。因为后面出现的偶数也已经计算完了,所以可以直接从前往后算。
额外需要注意的就是负数的情况。一开始取一个绝对值就好了。