#yyds干货盘点# 名企真题专题：小招喵跑步

1.简述：

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

小招喵想去的位置x

小招喵最少需要的步数

输入：

3

输出：

3

2.代码实现：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        if (x < 2 && x >= 0) {
            System.out.println(x);
            return;
        }
        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)/2] + 1 , dp[(i + 1) / 2] + 1) + 1;
            }
        }
        System.out.println(dp[x]);
    }
}