洛谷 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;
}

原文地址：https://blog.csdn.net/zqystca/article/details/144159363

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！