Untitled
unknown
plain_text
a year ago
774 B
3
Indexable
#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]; } };
Editor is loading...
Leave a Comment