Untitled

#define ll long long
class Solution {
public:
    unordered_map<ll,ll>dp;

    ll solve(ll n){
        if(n==1) return 0;
        if(dp.find(n)!=dp.end()) return dp[n];

        if(n%2==0) return dp[n]=1+solve(n/2);
        else return dp[n]=1+min(solve(n-1),solve(n+1));

    }
    int integerReplacement(int n) {
        ll a=n;
        return solve(a);
    }
};
------------------
class Solution {
public:
    int integerReplacement(int n) {
        vector<int>dp(n+2,INT_MAX);
        dp[1]=0;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            if(i%2==0) dp[i]=dp[i/2]+1;
            else{
                dp[i]=1+min(dp[i-1],(dp[(i+1)/2]+1)); //i+1 isnt yet initialized so we add +1 to its half and store
            }
        }
        return dp[n];
    }
};