题目链接
// 本题使用动态规划
#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;
}