题意：

给你一个数字 $图片说明$ ，你可以将当前数字 +1，将当前数字 -1，将当前数字 平方。
问最少操作多少次可以将数字 $图片说明$ 变换为数字 $图片说明$ ？

方法1（记忆化搜索）

我们设 $图片说明$ 表示将数字 $图片说明$ 变换为数字 $图片说明$ 的最少步数。
接下来我们分情况讨论。

n>=m时，如下图所示

显然有 $图片说明$ ，因为数字 $图片说明$ 想要变小只能每次减1 。
n<m时
第一种决策：将数字 $图片说明$ 加1，

即 $图片说明$
第二种决策：当时，将数字平方，

即
接下来我们考虑，能否考虑这个决策呢？
显然是不可以的，我们直接考虑一个简单的情况，依赖，而又依赖，这样就形成了一个环，如果这样决策，我们是无法求解答案的。
我们可以把这个数字 间接地 减小，我们考虑最优决策下，数字何时需要减小？
显然有一种情况，就是数字减小一些，再将其平方，使得其 更接近 数字。
例如：4要变成9，我们可以将4先减1，再将其平方，这样最接近9 。
那么我们可以考虑求出，将变为，再将变为，

即：

上述1表示将变为其平方的一次操作，表示将不足的数字每次+1的若干次操作。
还有一种情况，就是将一个数 平方后，再将其减小，例如：3变成8，可以将3先平方，后减1 。
对应的决策为：
当时，
代码：
```
class Solution {
public:
 int f[1001][1001];
 int dfs(int n,int m){
     if(n>=m)return n-m;//第一种情况
     if(f[n][m]!=-1)return f[n][m];//如果计算过，直接返回答案
     int res=dfs(n+1,m)+1;//第一种决策
     if(n*n!=n)res=min(res,dfs(n*n,m)+1);//第二种决策
     int t=sqrt(m);
     res=min(res,dfs(n,t)+1+(m-t*t));//详细见分析
     t++;
     if(t<m)res=min(res,dfs(n,t)+1+(t*t-m));
     return f[n][m]=res;
 }
 int solve(int n, int m) {
     memset(f,-1,sizeof f);//多测清空
     return dfs(n,m);
 }
};
```
时间复杂度：由于每对只会计算一次，故时间复杂度为。
空间复杂度：我们利用了一个二维数组来保存每对的答案，故空间复杂度为。
方法二：（广度优先搜索）

显然我们可以根据题意来构造一张起点为 $图片说明$ ，终点为 $图片说明$ 的隐式图，每条边 $(u,v)$ 表示数字 $u$ 变成数字 $v$ 的一个过程，且这张图中每条边权都为1，答案就是起点到终点的最短路径。
由于图中每条边权都为1，那么我们可以直接跑一遍广度优先搜索来求解答案。
代码：

class Solution {
public:
    bool vis[2001];//vis[i]表示数字i是否扩展过
    int dis[2001];//dis[i]表示数字n变换为数字i的最少操作次数
    int solve(int n, int m) {
        memset(vis,0,sizeof vis);
        memset(dis,0,sizeof dis);
        queue que;
        que.push(n);
        vis[n]=true;
        while(!que.empty()){
            int x=que.front();
            que.pop();
            if(x==m)return dis[x];
            if(x-1>=1&&!vis[x-1]){
                que.push(x-1);
                vis[x-1]=true;
                dis[x-1]=dis[x]+1;
            }
            if(x+1m时，因为要求最少操作次数，故没有扩展意义
                que.push(x+1);
                vis[x+1]=true;
                dis[x+1]=dis[x]+1;
            }
            if(x*x2*m时，我们要将x*x变为m需要超过m次操作，故没有扩展意义
                que.push(x*x);
                vis[x*x]=true;
                dis[x*x]=dis[x]+1;
            }
        }
        return 0;
    }
};

时间复杂度：由于这个隐式图的点数量是 $图片说明$ 级别的，搜索的过程中每个点只会扩展一次，故时间复杂度为 $图片说明$
空间复杂度：我们需要开数组记录每个点是否扩展过，记录起点到每个点的最短路径，故空间复杂度为 $图片说明$

题解 | #魔法数字#

题意：

方法1（记忆化搜索）

方法二：（广度优先搜索）