Clear C++ Solution Easy, but Would appreciate any Optimizations)


  • 0
    B
    int minCostII(vector<vector<int>>& costs) {
            int n = costs.size();
            if(n == 0)return 0;
            int k = costs[0].size();
            int dp[n][k];
            int ans = INT_MAX;
            
            for(int i = 0; i < k; i++){
                dp[0][i] = costs[0][i];
            }
            int l;
            priority_queue<int,vector<int>,std::greater<int>> min_heap;
            for(int i = 1; i < n; i++){
                l = 0;
                while(l < k){
                   
                for(int j = l; j < k-1; j++)
                  min_heap.push(dp[i-1][j+1]);
                
                
                    for(int m = 0; m < l;m++)
                         min_heap.push(dp[i-1][m]);
                 
                    int top = min_heap.top();
                   
                    dp[i][l] = costs[i][l] + top;
                    
                    while(!min_heap.empty()){
                        min_heap.pop();
                    }
                    l++;
                    
                }
            }
            for(int i = 0 ;i < k; i++)
                ans = min(ans,dp[n-1][i]);
         
         return ans;
        }

Log in to reply
 

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