Skip to content

256. Paint House 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  int minCost(vector<vector<int>>& costs) {
    for (int i = 1; i < costs.size(); ++i) {
      costs[i][0] += min(costs[i - 1][1], costs[i - 1][2]);
      costs[i][1] += min(costs[i - 1][0], costs[i - 1][2]);
      costs[i][2] += min(costs[i - 1][0], costs[i - 1][1]);
    }

    return *min_element(begin(costs.back()), end(costs.back()));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public int minCost(int[][] costs) {
    final int n = costs.length;

    for (int i = 1; i < n; ++i) {
      costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
      costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
      costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
    }

    return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def minCost(self, costs: List[List[int]]) -> List[List[int]]:
    for i in range(1, len(costs)):
      costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])
      costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])
      costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])

    return min(costs[-1])