【动态规划】CMB2 小招喵跑步

描述

小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：

1.数轴上向前走一步，即n=n+1 

2.数轴上向后走一步,即n=n-1 

3.数轴上使劲跳跃到当前点的两倍，即n=2*n

现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述：

小招喵想去的位置x

输出描述：

小招喵最少需要的步数

示例1

输入：

3

输出：

3

由题目得知道：

目标地址是x，如果x是负数，则从0到达x和到达-x的最少步数是完全一致的，为方便用数组表达，x<0时候 x=-x。

如果x是正数，可以知道每一步一直在坐标轴的右边是最快的走法，此时不用考虑地址落在负数不好用数组表达。所以有dp[1]=1.

如果i是偶数，则最快到达它的方法一定是 从i/2的位置，跳跃两倍，一步获取

如果i是奇数，则最快到达它的方法一定是 从（i-1）/2 或（ i+1）/2的位置跳跃两倍，然后+1或-1 走两步

至此可以推出dp公式：

dp[i] = dp[i / 2] + 1; 当i是偶数

dp[i] = Math.min(dp[(i - 1) / 2] , dp[(i + 1) / 2] ) + 2; 当i是计数

初始位置是0，所以有初始条件dp[0]=0;

代码：

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int x = in.nextInt();
            if (x < 0) x = -x;
            int[] dp = new int[x + 1];
            dp[0] = 0;
            if(x==0){
                System.out.println(dp[x]);
                return;
            }
            System.out.println(minSteps(x));
        }
    }

    public static int minSteps(int x){
        int[] dp=new int[x+1];
        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],dp[(i-1)/2])+2;
        }
        return dp[x];
    }

类似题目：

【动态规划】OD191. 求最小步数