#yyds干货盘点# 解决名企真题:小招喵跑步

1.描述:

描述

小招喵喜欢在数轴上跑来跑去,假设它现在站在点n处,它只会3种走法,分别是:1.数轴上向前走一步,即n=n+1 2.数轴上向后走一步,即n=n-1 3.数轴上使劲跳跃到当前点的两倍,即n=2*n现在小招喵在原点,即n=0,它想去点x处,快帮小招喵算算最快的走法需要多少步?

输入描述:

小招喵想去的位置x

输出描述:

小招喵最少需要的步数

示例1

输入:

3

输出:

3

2.代码实现:

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
System.out.println(solve(x));

}

public static int solve(int x){
if(x<2&&x>=0){
return x;
}
if(x < 0){
x = -x;
}
int[] dp=new int[x+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=x;i++){
if(i%2==0){
dp[i]=dp[i/2]+1;
}else{
dp[i]=Math.min(dp[i-1], 1 + dp[(i + 1) / 2])+1;
}
}
return dp[x];
}

}
发表评论

相关文章