Fast DP C++ solution utilize lambda function and for_each


  • 0
    W

    The algorithm I use is very similar to other solutions. Just want to provide an approach utilize standard library

    int minCostII(vector<vector<int>>& costs) {

        auto n = costs.size();
        if(!n) 
            return 0;
        auto k = costs[0].size();
    
        int prevMin(0), prevMin2(0), prevIdx(-1);
    
        for_each(costs.begin(), costs.end(), 
            [&](vector<int>& cost_row) {
                
                size_t counter = 0;
                int currMin(INT_MAX), currMin2(INT_MAX), currIdx(-1);
                
                for_each(cost_row.begin(), cost_row.end(), 
                    [&](int c){
                        c += (counter == prevIdx? prevMin2:prevMin);
                        if( c < currMin) {
                            currMin2 = (currMin);
                            currMin = c;
                            currIdx = counter;
                        }
                        else if ( c < currMin2) 
                            currMin2 = c;
                        counter ++;
                    }
                );
                prevMin = currMin;
                prevMin2 = currMin2;
                prevIdx = currIdx;
            }
        );
        
        return prevMin;
    

    }


Log in to reply
 

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