Integer Replacement(Leetcode 397

首先想到 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

1. 数组会很大（INT_MAX）
2. 数组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];
    }
};