题目来源
给一个数，求经过多少次变换变为1。
我一开始想着直接用DP，但是想想应该会内存溢出。
class Solution {
public:
int integerReplacement(int n) {
vector<int> dp(n+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最大也没多大，所以直接dfs不会有什么问题。
代码如下：
class Solution {
public:
int integerReplacement(int n) {
int cnt = 0;
return dfs(n);
}
int dfs(long long n)
{
if (n == 1)
return 0;
if (n % 2 == 0)
return dfs(n / 2) + 1;
else
return min(dfs(n+1), dfs(n-1)) + 1;
}
};
讨论区里利用了位操作来实现，不是很理解，不管它。
