题解 | #小招喵跑步#

#include <iostream>
using namespace std;

int f(int x){
    if(x < 3){
        return x;
    }
    else if(x % 2 == 0){
        // return f(x - 1) + f(x / 2);
        return  f(x/2) + 1;//偶数最小值是f(x/2)+1,只用看一半前的部分需要的步数
    }
    else if(x % 2 != 0){
        return min(f(x - 1), f(x + 1)) + 1;
    }
    return 0;//如果都不满足则为0
}

int main() {
    int n;
    cin >> n;
    if(n < 0){
        n = -n;//只考虑正数
    }
    int a = f(n);
    cout << a << endl;
    return 0;
}

使用动态规划思想，当x<3时(其实==3也行，代码忘记改了),x的值就是最小步数，大于这个数时，要想得到最小步数，就是看一半处的（越到后面，+1，-1会用的少），偶数就很简单，直接取一半，奇数分类讨论一半前是+1后的还是-1后的