题解 | #小招喵跑步# 动态规划

根据对称性，如果需要跳到负轴上，直接将其转为相反数

定义 dp[i] 为跳到 i 点时需要的最少步数

当 i 为偶数时，可以直接从 dp[i/2] 跳一步过来；

当 i 为奇数时，可以从 dp[i-1] 向前走一步过来，也可以从 dp[(i+1)/2] 跳一步到 dp[i+1] ，再退一步回到 dp[i] ，取较小值

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n < 0) {
            n = -n;
        }
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 1;
            } else {
                dp[i] = min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2);
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}

时间复杂度：O(n)，用于求 dp

空间复杂度：O(n)，用于存储 dp