小招喵跑步（动态规划）

题目

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

输入描述:
小招喵想去的位置x

输出描述:
小招喵最少需要的步数

示例1
输入

3

输出

3

题目链接

解题思路

很明显是一道动态规划题目
设dp[i]表示到达i点的最少步数
最少就需要考虑两倍的走法

• 如果当前位置能被2整除，说明可以转化为当前元素位置除以2之后的元素位置的最少步数+跳到本次位置的步数（1步）
  举个例子
  2 3 4 5 6
  如果从2开始出发到达4，4能被2整除，(dp[i] = dp[i/2]+1) 所以dp[4]=dp[2]+1，那dp[2]等于多少，还是这个思路，将一个大问题转化为n个小问题正是动态规划的魅力
  • 如果当前位置不能被2整除，那么就有2种选择了
    例如从2走到5
    （1）后退一步，满足跳2步，然后加上跳到本次的位置步数 dp[5]=dp[4]+1 (dp[i] = dp[i-1]+1)
    (2) 前进一步，满足跳2步， 然后回退到/2的位置，在前进一步 dp[5]=(dp[(5+1)/2]+1)+1=dp[3]+2 (dp[i]=dp[(i+1)/2]+1) + 1)

状态转移方程：

当前位置能被二整除，dp[i] = dp[i/2]+1;
当前位置不能被二整除，dp[i] = min(dp[i-1],dp[(i+1)/2]+1) + 1

代码

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

}