Evolve from brute force to optimal


  • 2
    1. O(2^n), try all combinations
        int minCost(vector<vector<int>>& costs) {
            return minCost(-1,-1,costs);
        }
        int minCost(int i, int j, vector<vector<int>>& costs) {
            if(i==costs.size()) return 0;
            int mc=INT_MAX;
            for(int k=0;k<3;k++) if(k!=j) mc = min(mc, minCost(i+1,k,costs));
            return i<0 ? mc : costs[i][j]+mc;
        }
    
    1. O(n) memoization
        int minCost(vector<vector<int>>& costs) {
            vector<vector<int>> mc(costs.size(),vector<int>(3));
            return minCost(-1,-1,costs,mc);
        }
        int minCost(int i, int j, vector<vector<int>>& costs, vector<vector<int>>& mc) {
            if(i==costs.size()) return 0;
            if(i>=0 && mc[i][j]) return mc[i][j];
            int cost=INT_MAX;
            for(int k=0;k<3;k++) if(k!=j) cost = min(cost, minCost(i+1,k,costs,mc));
            return i<0 ? cost : mc[i][j]=costs[i][j]+cost;
        }
    
    1. O(n) dp
        int minCost(vector<vector<int>>& costs) {
            int n = costs.size();
            vector<vector<int>> dp(n,vector<int>(3,INT_MAX));
            dp.push_back(vector<int>(3));
            for(int i=n-1;i>=0;i--) 
                for(int j=0;j<3;j++) { 
                    for(int k=0;k<3;k++) 
                        if(k!=j) dp[i][j] = min(dp[i][j],dp[i+1][k]);
                    dp[i][j]+=costs[i][j];
                }
            return min(dp[0][0],min(dp[0][1],dp[0][2]));
        }
    
    1. O(n) constant space dp. In #3, the current state is derived from the previous state only. So we don't need to cache all states.
        int minCost(vector<vector<int>>& costs) {
            int mc[3] = {0};
            for(auto &v:costs) {
                int t0 = mc[0], t1 = mc[1];
                mc[0] = v[0] + min(mc[1], mc[2]);
                mc[1] = v[1] + min(t0, mc[2]);
                mc[2] = v[2] + min(t0, t1);
            }
            return min(mc[0], min(mc[1], mc[2]));
        }
    

Log in to reply
 

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