40. 到达目的地的最短距离

// 本题使用动态规划
#include <bits/stdc++.h>
using namespace std;
 
int n;
 
void solve() {
    // 负数与正数答案一致
    n = abs(n); 
    int dp[n + 1];
    // 将dp数组元素初始化为0x3f3f3f3f
    // 可以理解为是一个极大值
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 1;
    dp[0] = 0;
    for(int i = 2; i <= n; ++i) {
        // 如果可以整除2, 那么+1或x2操作中的最小值
        if(i % 2 == 0) { 
            dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1);
        }
        // 为什么不用考虑dp[(i - 1) / 2] + 2的值
        // 因为肯定不会比dp[i - 1] + 1更小
        else {
            dp[i] = min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2);
        }
    }
    cout << dp[n] << endl;
}
 
int main()
{
    while(cin >> n) {
        solve();
    }
    return 0;
}

/*
反向bfs，leetcode加强版题目LCP 20. 快速公交
当x很大的时候，比如说1e9,使用楼上的动态规划显然是不现实的
如果是正向bfs的话，也会比较慢，可能也会遍历所有的点，因此这里使用反向bfs优先除以2
*/
#include <bits/stdc++.h>
using namespace std;
void solve() {
    int x;
    cin >> x;
    x = abs(x);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
    unordered_map<int,int>seen;
    pq.emplace(0,x);
    seen[x] = 0;
    // 最坏情况，每次+1到达x
    int ans = x;
    while(!pq.empty()) {
        auto [step,cur] = pq.top();
        pq.pop();
        // 若当前时间已经大于等于 全局最优时间，就没必要继续搜索了
        if(step >= ans) continue;
        // 若当前时间比 已记录的当前位置最小时间 大，则当前位置必然在之前有被搜索到，可跳过本轮
        if (step > seen[cur]) continue;
        // 同样用+1走完剩下的比较
        ans = min(ans, step+cur);
        int nxt = cur / 2;
        if(cur % 2) {
            // 能整除
            if (!seen.count(nxt) || step + 1 < seen[nxt]) {
                seen[nxt] = step + 1;
                pq.emplace(step + 1, nxt);
            }
        }else {
            // 不能整除有两种情况，一种是先+1再/2，一种是先-1再/2
            // 所以跳到的位置就是nxt和nxt+1
            if (!seen.count(nxt) || step + 2 < seen[nxt]) {
                seen[nxt] = step + 2;
                pq.emplace(step + 2, nxt);
            }
            if (!seen.count(nxt+1) || step + 2 < seen[nxt+1]) {
                seen[nxt+1] = step + 2;
                pq.emplace(step + 2, nxt+1);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

/**
 * 思路：使用动态规划解决
 * 
 * 确定 dp 数组以及下标的含义
 * 
 *   设 dp[i] 表达到 i 点的最少步数
 * 
 * 考虑状态转移方程
 * 
 *   一、如果当前的位置能够被 2 整除，只有一种走法
 *     从别的位置，通过在数轴上移动到当前位置数值的两倍方式移动过来的。
 *     dp[i] = dp[i / 2] + 1;
 * 
 *   二、如果当前的位置不能被 2 整数，有两种走法
 *     1. 通过在数轴上向前移动一格的方式移动过来的
 *     2. 通过在数轴上向后移动一格的方式移动过来的
 *     
 *     dp[i] = Math.min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1
 *   
 *     第 1 种走法为 dp[i - 1] 不难理解
 *     为什么第 2 种走法会是 dp[(i + 1) / 2] + 1 呢？
 *     因为如果当前位置不能被整除，那么这个位置的后一个位置必定能被整除，能被整除的坐标参考能被整除的走法。
 * 
 * 数组初始化
 *   
 *   1. 不要移动的情况 dp[0] = 0
 *   2. 只移动一步的情况 dp[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;
        }
        // 处理 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];
    }
}

#include <stdio.h>
#include <string.h>

int n;

void solve() {
    n = abs(n);
    int dp[n + 1];
    memset(dp, 0x3f, sizeof(dp));   // 将dp数组初始化为0x3f3f3f3f，表示极大值
    
    dp[1] = 1;                      // 边界条件
    dp[0] = 0;                      // 边界条件
    
    for(int i = 2; i <= n; ++i) {
        if(i % 2 == 0) {             // 如果可以整除2，执行+1或x2操作中的最小值
            dp[i] = (dp[i - 1] + 1) < (dp[i / 2] + 1) ? (dp[i - 1] + 1) : (dp[i / 2] + 1);
        }
        else {
            dp[i] = (dp[i - 1] + 1) < (dp[(i + 1) / 2] + 2) ? (dp[i - 1] + 1) : (dp[(i + 1) / 2] + 2);
        }
    }
    
    printf("%d\n", dp[n]);
}

int main() {
    while(scanf("%d", &n) == 1) {
        solve();
    }
    return 0;
}