C++ 0ms 11 lines "DP" solution


  • 5

    To me this is a very typical DP problem, so my initial approach was an O(n) DP solution as below, but it failed with LTE:

    int integerReplacement(int n) {
            int dp[n + 1]; memset(dp, 0, sizeof(dp));
            for (int i = 2; i <= n; i++) {
                dp[i] = 1 + (i & 1 == 0 ? dp[i / 2] : min(dp[i - 1], 1 + dp[i / 2 + 1]));
            }
            return dp[n];
    }
    

    Fortunately DP can always be done in a recursion way (with a hash table), and this gives me a chance to decrease the run time to somewhere between O(logn) and O(n):

    class Solution {
    private:
        unordered_map<int, int> visited;
    
    public:
        int integerReplacement(int n) {        
            if (n == 1) { return 0; }
            if (visited.count(n) == 0) {
                if (n & 1 == 1) {
                    visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
                } else {
                    visited[n] = 1 + integerReplacement(n / 2);
                }
            }
            return visited[n];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.