To me this is a very typical DP problem, so my initial approach was an O(n) DP solution as below, but it failed with LTE:

```
int integerReplacement(int n) {
int dp[n + 1]; memset(dp, 0, sizeof(dp));
for (int i = 2; i <= n; i++) {
dp[i] = 1 + (i & 1 == 0 ? dp[i / 2] : min(dp[i - 1], 1 + dp[i / 2 + 1]));
}
return dp[n];
}
```

Fortunately DP can always be done in a recursion way (with a hash table), and this gives me a chance to decrease the run time to somewhere between O(logn) and O(n):

```
class Solution {
private:
unordered_map<int, int> visited;
public:
int integerReplacement(int n) {
if (n == 1) { return 0; }
if (visited.count(n) == 0) {
if (n & 1 == 1) {
visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
} else {
visited[n] = 1 + integerReplacement(n / 2);
}
}
return visited[n];
}
};
```