题解 | #小招喵跑步#
小招喵跑步
http://www.nowcoder.com/practice/1177e9bd1b5e4e00bd39ca4ea9e4e216
正数和负数最少步数相同。
主要分为两种情况，n为偶数和n为奇数。
1.当n为偶数时，到达的方式两种，n-1，n/2；
2.当n为奇数时，到达方式两种，取最小。
（1）是直接从上一步n-1到达。
（2）因为n为奇数，先到达n+1偶数步，在往后退一步。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
n=abs(n);//正数和负数情况相同
int dp[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++){
if(i%2==0){
dp[i]=min(dp[i-1]+1,dp[i/2]+1);//当n为偶数，两种情况到达n-1，n/2
}else{
dp[i]=min(dp[i-1],dp[(i+1)/2]+1)+1;//当n为奇数，两种情况，n-1，或者是（n+1)/2-1步
} //这一步解释为，到达n+1偶数步，然后在后退一步
}
cout<<dp[n]<<endl;
return 0;
}
查看20道真题和解析