C语言 | Leetcode C语言题解之第397题整数替换

题目：

题解：

//第一种动态规划:超时
// 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);}
};