首先想到 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難想而且也過不了大數(shù)據(jù)（MLE）。

所以，如果題目滿足以下條件，就用memorized search instead of DP

1. 數(shù)組會很大（INT_MAX）
2. 數(shù)組index并不會單調遞增（此題，i取決于i-1, 和i+1），需要未來條件
3. 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];
    }
};