为什么同样是记忆化搜索，我就用了将近100倍的时间？

class Solution {
public:
    unordered_map<int, int> memo;
    int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n == INT_MAX) return 32;


        if (memo.count(n)) return memo[n];
        int res = 0;
        if (n & 1) {
            res = 1 + min(integerReplacement(n - 1), integerReplacement(n + 1));
        } else {
            res = 1 + integerReplacement(n >> 1);
        }
        memo[n] = res;
        return res;
    }
    /////   以上是题解（只用了4ms）     ///////////////

    vector<int> cache;
    int integerReplacement(int n) {
        if(n==INT_MAX) return 32;
        int i=0;
        while(n%2==0){
            n=n/2;
            i++;
        }
        cache = vector<int>(n+2,-1);
        return dfs(n)+i;
    }
    int dfs(int n) {
        if(n==1) return 0;
        if(cache[n]!=-1) return cache[n];

        if(n%2==0) cache[n] = dfs(n/2)+1;
        else cache[n] = min(dfs(n+1),dfs(n-1))+1;

        return cache[n];
    }
    ////   上面是我自己写的感觉思路一样但我用了400ms！！   //////
};

需要注意到n的范围比较大，最高能到达int的最大值，2e9左右
你的vector是根据n进行开空间的，虽然前面对n进行了处理（一直除2到奇数），但是在数据构造为奇数的情况下仍然得开大空间
以下测试为测试代码，功能为测试vector开空间以及赋值需要多少时间
这里测试情况在0.26s（260ms）的时候就会断言失败了

double st = clock();
cache = vector<int>(n+2,-1);
double ed = clock();
if (ed - st <= CLOCKS_PER_SEC*0.26) {
    printf("%d", n);
}
assert(ed - st <= CLOCKS_PER_SEC*0.26);

数据为 111111111，这里刚好是9个1，大数据的时候，明显会存在问题

但是如果用unordered_map就不一样了，这个底层为哈希表，而且是动态开空间，查询复杂度和插入复杂度理论都是O(1)

我觉得直接递归应该快一点

为什么都是记忆化搜索，博主的程序运算时间要明显长呢？
1）用了不必要的递归函数dfs(int)。程序设计的一个原则是，能用循环处理的，就尽量不用递归去处理。因为递归每执行一次，都要在堆栈上进行最少一次函数调用的出入栈操作，这种时间和内存的花销显然不会少。这是其一。另外博主这部分相关逻辑上，本身都类似，却一半是循环一半是递归，也实在让人有点眼花缭乱。
2）这个题目最多的运算逻辑，都在循环里那部分，都是位操作就可以完成的，位操作一般来说肯定比一般的运算操作要更有效率。这是其二。
3）用来记忆的vector的查询效率，尤其是无序的，应该是比unordered_map差的。 这是其三。
4）if(n==1) return 0; 这个一次就可以，博主确在每次的递归中都重复一次。这是其四。当然，如果不递归可能就不用了。
总体感觉，从博主的程序上看，博主C++ 的技能多多，但却忘了一项软技能，那就是 “省事”。
正解答案已经很优化了！没必要再去琢磨，当然除了学习它~

不好意思，刚看错了，正解答案也用递归函数了但没用循环。
那原因应该就是上述 2） 3） 以及1）4）当中的重复计算部分，其实正解的递归也是可以优化掉的。