vivek_ragi

PaintHouse

Jun 6th, 2021 (edited)
49
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minCostII(vector<vector<int>>& costs) {
  4.         //bottom up
  5.         int n = costs.size();
  6.         int k = costs[0].size();
  7.         for(int i = 1; i < n; i++) //houses
  8.         {
  9.             // here you need to compute min and second min from the previous row
  10.             int mn = INT_MAX;
  11.             int sec_min = INT_MAX;
  12.             for(int j = 0; j < k; j++) //colors
  13.             {
  14.                 if(costs[i-1][j] < mn)
  15.                 {
  16.                     mn = costs[i-1][j];
  17.                 }
  18.                 if(costs[i-1][j] > mn and costs[i-1][j] < sec_min)
  19.                 {
  20.                     sec_min = costs[i-1][j];
  21.                 }
  22.             }
  23.            
  24.             //we have min and sec_min
  25.            
  26.             for(int j = 0; j < k; j++)
  27.             {
  28.                 if(costs[i - 1][j] == mn)
  29.                 {
  30.                     costs[i][j] += sec_min;
  31.                 }
  32.                 else
  33.                 {
  34.                     costs[i][j] += mn;
  35.                 }
  36.             }
  37.         }
  38.        
  39.         //now compute min in last row
  40.        
  41.         int ans = INT_MAX;
  42.         for(int j = 0; j < k; j++)
  43.         {
  44.             ans = min(ans, costs[n - 1][j]);
  45.         }
  46.        
  47.         return ans;
  48. }
  49. };
RAW Paste Data