C++ DP time O(nk) space O(k)


  • 21
    K

    maintain the minimum two costs min1(smallest) and min2 (second to smallest) after painting i-th house.

    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n==0) return 0;
        int k = costs[0].size();
        if(k==1) return costs[0][0];
    
        vector<int> dp(k, 0);
        int min1, min2;
    
        for(int i=0; i<n; ++i){
            int min1_old = (i==0)?0:min1;
            int min2_old = (i==0)?0:min2;
            min1 = INT_MAX;
            min2 = INT_MAX;
            for(int j=0; j<k; ++j){
                if(dp[j]!=min1_old || min1_old==min2_old){
                    dp[j] = min1_old + costs[i][j];
                }else{//min1_old occurred when painting house i-1 with color j, so it cannot be added to dp[j]
                    dp[j] = min2_old + costs[i][j];
                }
    
                if(min1<=dp[j]){
                    min2 = min(min2, dp[j]);
                }else{
                    min2 = min1;
                    min1 = dp[j];
                }
            }
        }
    
        return min1;
    }

  • 3

    Hi, kelly. Great code! Very nice idea to maintain only the smallest two elements. Thanks for your sharing! BTW, I rewrite your code a little bit . Hope it is Ok :-)

    class Solution {
    public:
        int minCostII(vector<vector<int>>& costs) {
            if (costs.empty()) return 0;
            int n = costs.size(), k = costs[0].size(), m1 = 0, m2 = 0;
            vector<int> dp(k, 0);
            for (int i = 0; i < n; i++) {
                int t1 = m1, t2 = m2;
                m1 = m2 = INT_MAX;
                for (int j = 0; j < k; j++) {
                    dp[j] = (dp[j] != t1 ? t1 : t2) + costs[i][j];
                    if (m1 <= dp[j]) m2 = min(m2, dp[j]);
                    else m2 = m1, m1 = dp[j];
                }
            }
            return m1;
        }
    }; 

  • 8
    B

    Really brilliant idea to maintain only the two smallest total costs until the previous house! Otherwise we might need to traverse the other k-1 colors for each j, and the time complexity would be O(nk^2).

    However, the extra O(k) space could have been reduced. We can record both the min value and its color index in the previous row. Thus when we traverse the k colors for house i, we can decide whether to adopt min1 by comparing j == min1Idx.

    Please check out the code below, which is O(nk) time and O(1) auxiliary space.

    struct Position {
        int index;
        int value;
        Position (int _i, int _v) : index (_i), value (_v) {}
    };
    
    //(nk) time O(1) auxiliary space;
    int minCostIIOptimized (vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) {
            return 0;
        }
        
        //I think it's better to return 0 when painting 
        //more than 1 houses with a single color;
        int k = costs[0].size();
        if (k == 1) {
            return n == 1 ? costs[0][0] : 0;
        }
        
        Position min1 (-1, 0), min2 (-1, 0);
        for (int i = 0; i < n; i++) {
            Position tmp1 = min1, tmp2 = min2;
            min1.value = INT_MAX;
            min2.value = INT_MAX;
            for (int j = 0; j < k; j++) {
                int cost = (j != tmp1.index ? tmp1.value : tmp2.value) + costs[i][j];
                
                //update the min1 and min2 of the current row;
                if (cost < min1.value) {
                    min2 = min1;
                    min1 = Position (j, cost);
                } else if (cost < min2.value) {
                    min2 = Position (j, cost);
                }
            }
        }
        
        return min1.cost;
    }

  • 0
    K

    I think you got a more efficient solution!!


  • 0
    B

    Thank you very much Kelly! But I have to say your idea to maintain min1 and min2 is really insightful and smart!!!


  • 0
    B
    This post is deleted!

  • 0
    A

    Excellent! ^.^ Thanks!


  • 0
    M

    I think the condition dp[j]!=min1_old || min1_old==min2_old should be replaced by dp[j]!=min1_old although it will not change the results


  • 0
    Y

    When min1old==min2old, either way is ok.


  • 0
    T

    min1 and min2 should store the index of color, instead of the cost of those two colors.


Log in to reply
 

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