```
class Solution(object):
def integerReplacement(self, n):
memo = {1 : 0}
def helper(m):
if m not in memo:
# From an odd number m, you must jump to (m - 1) / 2 or (m + 1) / 2 using two steps
memo[m] = helper(m // 2) + 1 if m % 2 == 0 else min(helper((m - 1) / 2), helper((m + 1) / 2)) + 2
return memo[m]
return helper(n)
```

The idea is simple, if n is an even integer, then the minimum number of replacement is the number of n / 2 plus one; if n is an odd integer, then the minimum number of replacement is the smaller for n + 1 and n - 1 plus one.

Here, memoization is used to save some space because some cases are never reached. e.g. helper(7)->helper(4)->helper(2)->helper(1), helper(7)->helper(3)->helper(2)->helper(1), helper(7)->helper(3)->helper(1). 5 is not called. The called numbers will be more sparse with larger n.