C++ 3ms solution, divide conquer + memoization


  • 0
    B
    class Solution {
    public:
        int getMoneyAmount(unordered_map<int,int>& mm, int base, int lo, int hi) {
            int key = lo * base + hi;
            if (mm.find(key) != mm.end())
                return mm[key];
    
            int n = hi - lo + 1;
    
            if (n <= 1)
                return 0;
            else if (n <= 2)
                return lo;
    
            int res = INT_MAX;
            for (int i = hi - 1; i >= lo; i -= 2) {
                int t = i + max(getMoneyAmount(mm, base, lo, i - 1),
                                getMoneyAmount(mm, base, i + 2, hi));
                if (t > res)
                    break;
                res = t;
            }
    
            return mm[key] = res;
        }
        
        int getMoneyAmount(int n) {
            unordered_map<int,int> mm;
            return getMoneyAmount(mm, n + 1, 1, n);
        }
    };
    

Log in to reply
 

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