A much faster C++ solution than DP


  • 0
    H

    Intuitively, to minimize cost, you should always first choose a number in larger half range, i.e. find the weighted balance point

    class Solution {
    public:
        int getMoneyAmount(int n) {
            vector<vector<int>> cache(n+1, vector<int>(n+1, 0));
            return cost(cache, 1, n);
        }
        
        int cost(vector<vector<int>>& v, int l, int r) {
            if (l >= r) return 0;
            if (v[l][r] != 0) return v[l][r];
            int res = INT_MAX;
            int start = l + (r - l) / 2;
            for (int i = start; i <= r; ++i) {
                int lc = cost(v, l, i-1);
                int rc = cost(v, i+1, r);
                int tmp = i + std::max(lc, rc);
                res = std::min(res, tmp);
                if (lc >= rc) break;
            }
            v[l][r] = res;
            return res;
        }
    };
    

Log in to reply
 

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