题目:
题解:
//第一种动态规划:超时
// class Solution {
// public:
// int integerReplacement(int n) {
// vector<int>dp(n+1,0);
// dp[1]=0;
// for(int i=2;i<=n;i++){
// if(i%2==0){
// dp[i]=dp[i/2]+1;
// }
// else{
// dp[i]=min(dp[i-1],dp[(i+1)/2]+1)+1;
// }
// }
// return dp[n];
// }
// };
//第二种:递归。这里需要注意一下就是int数据溢出的问题。
class Solution{
public:long Solve(long num){if(num==1){return 0;}if(num%2==0){return Solve(num/2)+1;}else{return (long)min(Solve(num-1),Solve(num+1))+1;}}int integerReplacement(int n){long num=n;return Solve(num);}
};