首先想到 memorized search
最后一个test case是INT_MAX...拿出来单独讨论：
unordered_map<int, int> mp;
int integerReplacement(int n) {
if(n == 1) return 0;
else if(n == INT_MAX) return 32;
if(mp.count(n)) return mp[n];
if(n % 2 == 0) {
mp[n] = integerReplacement(n/2) + 1;
}else{
mp[n] = min(integerReplacement(n+1), integerReplacement(n-1)) + 1;
}
return mp[n];
}
};
既然有memorized search，于是便想到用DP试试。但DP难想而且也过不了大数据（MLE）。
所以，如果题目满足以下条件，就用memorized search instead of DP
- 数组会很大（INT_MAX）
- 数组index并不会单调递增（此题，i取决于i-1, 和i+1），需要未来条件
- memorized search更加直观明确
以下是DP的代码
class Solution {
public:
int integerReplacement(int n) {
if(n <= 1) return 0;
else if(n == INT_MAX) return 32;
vector<int> dp(n+2, n+2);
dp[1] = 0, dp[2] = 1;
for(int i=2; i<n+2; i++){
if(i % 2 == 0 && dp[i] > dp[i/2] + 1) dp[i] = dp[i/2]+1;
if(i+1 <= n+1 && dp[i] > dp[i+1] + 1) dp[i] = dp[i+1] + 1;
if(i % 2 == 0){
if(i+1 <= n+1) dp[i+1] = min(dp[i+1], dp[i]+1);
dp[i-1] = min(dp[i-1], dp[i]+1);
}
}
return dp[n];
}
};
