洛谷 B3626 跳跃机器人 C语言 记忆化搜索
题目：
https://www.luogu.com.cn/problem/B3626
题目描述
地上有一排格子，共 n 个位置。机器猫站在第一个格子上，需要取第 n 个格子里的东西。
机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：
- 初始时，机器人位于 1 号格子
- 若机器人目前在 x 格子，那么它可以跳跃到 x−1,x+1,2x 里的一个格子（不允许跳出界）
问机器人最少需要多少次跳跃，才能到达 n 号格子。
输入格式
仅一行，一个正整数，表示 n。
输出格式
仅一行，一个正整数，表示最少跳跃次数。
思路：很明显的记忆化搜索和dp，但是由于题目给的搜索方向是x-1和x+1，正序写会造成死循环，所以有什么方法吗？我们可以倒序写，因为除以2在这三个搜索方向中优先级是最高的，所以是不需要min的，而且，x+1，x-1。都会出现偶数，然后进行除以2，所以不会死循环。
代码如下：
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long ll;
ll mem[2000000];
ll n;
ll dfs(ll n)
{
ll sum = 0;
if (n < 1)
return INT_MAX;//代表不可能
if (n == 1)
return 0;//基准条件
if(mem[n])
return mem[n];
else
{
if (n % 2 == 0)//已是最优解 ,优先级更高原因是防止死循环(仅限这个题目x+1,x-1)
sum = dfs(n / 2) + 1;
else
{
sum = min(dfs(n+1)+1,dfs(n-1)+1);
}
}
mem[n] = sum;
return sum;
}
int main(void)
{
cin >> n;
cout << dfs(n);
return 0;
}