难度中等
给定一个正整数 n ，你可以做如下操作：
- 如果
n是偶数，则用n / 2替换n。 - 如果
n是奇数，则可以用n + 1或n - 1替换n。
返回 n 变为 1 所需的 最小替换次数 。
示例 1：
输入：n = 8 输出：3 解释：8 -> 4 -> 2 -> 1
示例 2：
输入：n = 7 输出：4 解释：7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1
示例 3：
输入：n = 4 输出：2
class Solution: def integerReplacement(self, n: int) -> int: def backtracking(n,momo): if n == 1: momo[n] = 1 return 1 if n <=0: return 0 if n%2==1: res = 1 + min(backtracking(n+1,momo),backtracking(n-1,momo)) else: res = 1 + backtracking(n/2,momo) momo[n] = res return res momo = {} return backtracking(n,momo)-1