洛谷 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，以是不会死循环。
代码如下：

1. #include<iostream>
2. #include<algorithm>
3. #include<climits>
4. using namespace std;
5. typedef long long ll;
6. ll mem[2000000];
7. ll n;
8. ll dfs(ll n)  
9. {
10.         ll sum = 0;
11.         if (n < 1)
12.         return INT_MAX;//代表不可能  
13.         if (n == 1)
14.         return 0;//基准条件
15.         if(mem[n])
16.         return mem[n];     
17.         else
18.         {
19.                 if (n % 2 == 0)//已是最优解 ,优先级更高原因是防止死循环(仅限这个题目x+1,x-1)
20.                 sum = dfs(n / 2) + 1;
21.                 else   
22.                 {
23.                          sum = min(dfs(n+1)+1,dfs(n-1)+1);
24.                 }
25.         }
26.         mem[n] = sum;
27.         return sum;
28. }
29. int main(void)
30. {
31.         cin >> n;
32.         cout << dfs(n);
33.         return 0;
34. }

复制代码