题意概述

• 给定两个数字n，m
• 每次对n进行一次操作，可对其自加，自减，平方
• 问至少多少次操作可使n=m

方法一：BFS

思路与具体做法

• 如果n>=m，n缩小只有通过自减来实现，直接返回n-m即可
• 广度优先搜索，每次对队首元素分别进行自增，自减，平方后加入队列，同时对操作后的数继承队首元素深度值+1
• 最后总的操作次数即dp[m]

class Solution {
public:
    int solve(int n, int m) {
        if(n>=m)return n-m;
        queue<int>q;
        map<int,int>d;//当前数字，深度
        q.push(n);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(u==m)return d[m];
            if(u<m){
                if(!d[u+1]){q.push(u+1);d[u+1]=d[u]+1;}
                if(!d[u*u]){q.push(u*u);d[u*u]=d[u]+1;}
            }
            if(!d[u-1]){q.push(u-1);d[u-1]=d[u]+1;}
        } 
        return d[m];
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，最坏情况下，m>n，只能n不断自增
空间复杂度：，最下情况下用到了长度为m-n的队列和map映射

方法二：DFS

思路与具体做法

• 如果n>=m，n缩小只有通过自减来实现，直接返回n-m即可
• 因为平方是增长最快的方式，所以优先平方操作，我们找n^k<=m<=n^(k+1)或sqrt(m)<=n<=sqrt(m)+1，并比较n平方后的左右值哪一个更加接近m或m开方后的左右值哪一个跟加接近n
• 此时就不需再有平方操作了，仅能通过n自增自减来实现向m的逼近
  接着不断递归直到n==m即可

class Solution {
public:
    int solve(int n, int m) {
        if(n>=m)return n-m;//n>=m时，变小方式只有n自减 
        int k=sqrt(m);//对m开方，操作步骤+1，且k略小于m开方 
        if(m-k*k>(k+1)*(k+1)-m){//k从左右两个方向逼近m,选取距离最近的那一个 
            k++;
        }
        int ans=abs(m-k*k);//此时已不能再平方，只能m自增或自减，步骤+abs(m-k*k) 
        return min(m-n,solve(n,k)+ans+1);//向下递归
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，最坏情况下，m>n，只能n不断自增
空间复杂度：，最坏情况下，需要m-n深度的递归栈