给定一个正整数 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
解法：
模拟（递归+记忆化搜索）
public class Solution {public int integerReplacement(int n){return dfs(n*1l);}public int dfs(long n){if(n==1){return 0;}if(n%2==0){return 1+ dfs(n/2);}else {return 1+Math.min(dfs(n-1),dfs(n+1));}}public static void main(String[] args) {Solution solution=new Solution();int n= 8;System.out.println(solution.integerReplacement(n));}
}
