class Solution {
public int integerReplacement(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return dfs(memo, n);
}
private int dfs(Map<Integer, Integer> memo, int n){
if(n==1){
return 0;
}else if (memo.containsKey(n)){
return memo.get(n);
}
int res;
if (n%2==0){
res = dfs(memo, n/2)+1;
}else{
res = Math.min(dfs(memo, n/2), dfs(memo, n/2+1))+2;
}
memo.put(n, res);
return res;
}
}