题解 | #小招喵跑步#

• 这道题有大佬已经讲解的很好了，我想说的是
• 如果当前位置不能被2整除的时候，到达i位置有两种情况：
• （1）i-1满足当前位置为偶数，然后加上跳到本次的位置步数 dp[i]=dp[i-1]+1,这里还可以写成：dp[i]=dp[(i-1)/2] + 1 + 1;
• （2）i+1满足当前位置为偶数， 然后回退到(i+1)/2的位置，有dp[i]=(dp[(i+1)/2]+1) + 1)

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]);
    }
}