Integer Replacement

题目来源
给一个数，求经过多少次变换变为1。
我一开始想着直接用DP，但是想想应该会内存溢出。

class Solution {
public:
    int integerReplacement(int n) {
        vector<int> dp(n+1, 0);
        for (int i=2; i<=n; i++) {
            if (i % 2 == 0)
                dp[i] = dp[i/2] + 1;
            else
                dp[i] = min(dp[i-1], dp[(i+1)/2]+1) + 1;
        }
        return dp[n];
    }
};

然后果然就溢出了。
然后实际上想想，如果从指数级别来看的话，int最大也没多大，所以直接dfs不会有什么问题。
代码如下：

class Solution {
public:
    int integerReplacement(int n) {
        int cnt = 0;
        return dfs(n);
    }
    
    int dfs(long long n)
    {
        if (n == 1)
            return 0;
        if (n % 2 == 0)
            return dfs(n / 2) + 1;
        else
            return min(dfs(n+1), dfs(n-1)) + 1;
    }
};

讨论区里利用了位操作来实现，不是很理解，不管它。