The basic idea is to use recursion with memory since there are many duplicated sub-cases.

To avoid the INT_MAX case, we just go step further with 1 + res[1+(n/1)] instead of res[n+1)/2]

```
int integerReplacement(int n) {
if(n==1) return 0;
else if(n==2) return 1;
static unordered_map<int, int> map_n_cnt;
if( map_n_cnt[n] != 0 ) return map_n_cnt[n];
if( (n&1) == 0 ) {
map_n_cnt[n] = 1 + integerReplacement(n>>1);
return map_n_cnt[n];
}
else{
map_n_cnt[n] = 1 + std::min( integerReplacement(n-1), 1+integerReplacement(1+(n>>1)) );
return map_n_cnt[n];
}
}
```