Evolve from brute force to optimal


  • 2

    This is similar to paint house.

    1. O((k-1)^n) brute force
        int minCostII(vector<vector<int>>& costs) {
            if(costs.empty()) return 0;
            return minCost(-1,-1,costs);        
        }
        int minCost(int i,int j, vector<vector<int>>& costs) { //minCost starting from house i with color j
            if(i==costs.size()) return 0;
            int mc = INT_MAX;
            for(int k=0;k<costs[0].size();k++) if(k!=j) mc = min(mc, minCost(i+1,k,costs));
            return i<0? mc : mc+costs[i][j];
        }
    
    1. O(nk^2) Memoization
        int minCostII(vector<vector<int>>& costs) {
            if(costs.empty()) return 0;
            vector<vector<int>> mem(costs.size(),vector<int>(costs[0].size()));
            return minCost(-1,-1,mem,costs);        
        }
        int minCost(int i,int j, vector<vector<int>>& mem, vector<vector<int>>& costs) {
            if(i==costs.size()) return 0;
            if(i>0 && mem[i][j]) return mem[i][j];
            int mc = INT_MAX;
            for(int k=0;k<costs[0].size();k++) if(k!=j) mc = min(mc, minCost(i+1,k,mem,costs));
            return i<0? mc : mem[i][j]=mc+costs[i][j];
        }
    
    1. O(nk^2) dp
        int minCostII(vector<vector<int>>& costs) {
            if(costs.empty()) return 0;
            int n = costs.size(), k = costs[0].size();
            vector<vector<int>> dp(n+1,vector<int>(k));
            for(int i=n-1;i>=0;i--)
                for(int j=0;j<k;j++)
                    dp[i][j]=getMin(j,dp[i+1]) + costs[i][j];
            return getMin(-1, dp[0]);        
        }
        int getMin(int j, vector<int> &pre) {
            int mc = INT_MAX;
            for(int i=0;i<pre.size();i++) if(i!=j) mc = min(mc,pre[i]);
            return mc;
        }
    
    1. O(nk) dp
        int minCostII(vector<vector<int>>& costs) {
            int pre1=0,pre2=0,c1=-1;
            for(auto &v:costs) {
                int cur1=INT_MAX,cur2,co1;
                for(int i=0;i<v.size();i++) {
                    int c = v[i]+ (i==c1?pre2:pre1);
                    if(c<cur1) {
                        cur2 = cur1;
                        co1 = i;
                        cur1 = c;
                    } else if (c<cur2) cur2 = c;
                }
                pre1 = cur1;
                pre2 = cur2;
                c1 = co1;
            }
            return pre1;
        }
    

  • 0
    H

    Your solution 1 and 2 doesnt seem to work in the tests..
    theres a integer overflow issue..


  • 0

    @henry19 I cannot access the problem. What is the test case that overflows? Changing mc from int to long may fix it.


Log in to reply
 

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