397. Integer Replacement!

dp+recursion

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;                   
    }
}