难度中等
给定一个正整数 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
标签：示例,int,整数,momo,397,替换,def From： https://www.cnblogs.com/zle1992/p/17452905.html